Espero que no los hayan visto.
(1) Digamos que hay un círculo dividido en $n$ secciones (sectores). Pablito empieza en la sección 1. Empieza a brincar, y en cada brinco, salta a la sección siguiente, o a la que le sigue a la siguiente. Entonces hay $2n$ movimientos posibles, 2 por cada sección. Entonces, empieza a brincar y da 2 vueltas, y vuelve a llegar al sector 1. No repitió movimientos. ¿De cuántas maneras pudo haber hecho esto Pablo?
REFORMULACIÓN:
¿De cuántas maneras puede dar exactamente 2 vueltas sin repetir movimientos?
(2) Hago un triángulo de Pascal con $n$ filas. Sobre cada casilla de él, coloco una dama inglesa blanca. Pablo escoge una línea (en total hay $3n$ posibles), y voltea todas las fichas sobre esa fila (blanca -> negra, negra -> blanca). A cada configuración a la que se puede llegar de damas inglesas $C$, llamo $f(C)$ al mínimo número de movimientos necesitados para llegar a ella. Para cada $n$, determina el máximo valor finito posible de $f(C)$.
Si ya los vieron, me dicen.
lunes, 13 de mayo de 2013
Suscribirse a:
Comentarios de la entrada (Atom)
6 comentarios:
En el $2$ quiere decir que $f\left(C\right)$ es la cantidad mínima de movimientos que se necesitan para llegar de la configuración inicial (todas las piezas blancas) a $C$ ?
Sípi.
en el primero creo que viendo que siempre sin importar el orden de los movimientos y no se repiten se llega a dar 3 vueltas. se puede ver suponiendo que no. y asi ya solo se cuentan las formas de dar una vuelta
Sólo se dan 2 vueltas, no 3. No entiendo.
Para el segundo, primero que nada, vemos que las configuraciones que dejan todo blanco son no hacer nada, hacer todas las de dos direcciones y en cada dirección hacer una sí y una no tal que dos vertices esten "tapados" en esa dirección. De hecho, la de todas las de dos direcciones es igual que esta ultima.
Esto lo podemos ver haciendo los casos empezando de suponer que un vertice esta tachado con la dirección que solo lo cubre a este y vamos viendo que en cada punto en cada dirección debería haber dos encendidas.
Es facil ver que el máximo es menor a $3n/2$, porque si hay $a,b,c$ de cada dirección, aplicandole una de que se queden todos blancos extra, podemos llegar a la misma configuración con $n-a,n-b,c$ y si SGP $a+b\geq n+1$ entonces $n-a,n-b,c$ tendrá a $n-a+n-b\leq n-1$. Entonces es cota maxima.
Bueno, basicamente esa es la idea y te sale algo como piso de $3n/2$, al rato pongo la cuentas.
Según yo la parte difícil es encontrar la cota mínima.
Publicar un comentario