Se tiene un salón con un acomodo de asientos de $m\times 2$. Hay un alumno sentado en cada asiento. El profesor les pide a los alumnos que cambien de lugar al dar una señal. La condición para cambiar es que se muevan a un asiento que esté a la izquierda, derecha, enfrente o atrás del suyo.
¿De cuántas formas puede ocurrir este cambio si al final también queda un alumno en cada asiento?
martes, 27 de marzo de 2012
Suscribirse a:
Comentarios de la entrada (Atom)
18 comentarios:
Diremos que hay $m$ columnas y $2$ filas.
Primero veremos como se comportan los cambios entre alumnos.
Si hay $2$ alumnos $A$ y $B$ en asientos de una misma columna que intercambian lugar entre ellos. Entonces estos $2$ alumnos dividen en $2$ partes a los otros alumnos, pues ningún otro alumno puede intercambiar lugares con $A$ y $B$, sin poder pasar al otro lado de los asientos que determinan $A$ y $B$.
Si hay $2$ alumnos $C$ y $D$ tales que tienen asientos consecutivos en la misma fila (sin pérdida de la generalidad, digamos que es la fila inferior), y entre ellos cambian de lugar. Entonces si $C_{1}$ y $D_{1}$ son los alumnos en la misma columna que $C$ y $D$ respectivamente, $C_{1}$ y $D_{1}$ deben intercambiar lugar entre si. Supongamos que no lo hacen. Entonces $C_{1}$ intercambia lugar con el único otro alumno con el que puede intercambiar (No $C$ ni $D_{1}$) y luego, ese alumno debe intercambiar lugar con otro alumno distinto a todos los demás con los que se ha intercambiado lugar haciendo una cadena, que es finita, y no es posible cerrar, pues al momento en que $C_{1}$ no intercambia lugar con $D_{1}$, los asientos quedan divididos en $2$ regiones ajenas, y eventualmente habría un alumno el cual no podría intercambiar lugar, lo cual es una contradicción. Hacemos análogamente asumiendo que $D_{1}$ no intercambia lugar con la silla donde estaba $C_{1}$ y llegamos a contradicción. Entonces $C_{1}$ y $D_{1}$ deben intercambiar lugar entre si.
Entonces es fácil ver que si ya contamos todas las construcciones como las anteriores $2$ mencionadas, todo lo que resta con respecto a los cambios entre alumnos serán ciclos, con $2$ posibles direcciones, pues tomamos una región libre de las construcciones arriba mencionadas, y es fácil ver que como no hay $2$ alumnos que intercambien lugar entre si, deben hacerse cadenas de intercambio, que deben cerrarse en algún punto,pudiendo hacer varias cadenas.
Ahora, sea
$F=\left\{f_{1}, f_{1},\ldots ,f_{k},\ldots \right\}=\left\{1, 1, 2, 3, 5,\ldots \right\}$
la sucesión de Fibonacci. Probaremos que para $m$ columnas, la cantidad de maneras de hacer lo requerido es $f_{m}^{2}$.
Ahora, sea $F=\left\{f_{0}, f_{1},\ldots ,f_{k},\ldots \right\}=\left\{1, 1, 2, 3, 5,\ldots \right\}$ la sucesión de Fibonacci.
Probaremos que para $m$ columnas, la cantidad de maneras de hacer lo requerido es $f_{m}^{2}$.
Procederemos por inducción fuerte sobre $m$. Es fácil ver que si $m=1, 2$ entonces la cantidad de maneras de hacer lo requerido es $1$ y $4$ respectivamente, que son $f_{1}^{2}$ y $f_{2}^{2}$ respectivamente. Ahora, supongamos que para todo $i\leq k$ tenemos que la cantidad buscada para $i$ columnas es $f_{i}^{2}$. Entonces veamos como se comportarán los rectángulos de $k+1$ columnas. Veamos que el extremo izquierdo se comportará de una de $3$ maneras
- Los $2$ alumnos en la columna izquierda intercambian lugar entre si.
- Los $2$ alumnos en la columna izquierda intercambian lugar con el respectivo alumno que tienen a su derecha.
- Se hace un ciclo en la parte más izquierda del rectángulo de $k+1$ columnas, pasando por los $2$ alumnos en la columna izquierda.
En el primer caso, claramente faltan elegir $k$ columnas, y por hipótesis de inducción, esto se hace de $f_{k}^{2}$ maneras.
En el segundo caso, claramente faltan elegir $k-1$ columnas, que por hipótesis de inducción se hace de $f_{k-1}^{2}$ maneras posibles.
En el tercer caso, veamos que este ciclo puede abarcar desde $2$ hasta $k+1$ columnas. Entonces tendremos que Si abarca $j$ columnas, entonces quedan $k+1-j$ columnas por elegir, que se hace de $f_{k+1-j}^{2}$ maneras. Pero Notemos que los ciclos tienen $2$ direcciones, y entonces la cantidad de maneras de hacer lo que queremos es
$2\sum_{s=1}^{k-1}{f_{s}^{2}}=2f_{k-1}f_{k}$.
Entonces, como los $3$ casos anteriores son ajenos entre si, pues ningún rectángulo comienza en la izquierda con la misma configuración en casos distintos, tenemos que el total de maneras de hacer lo requerido por el problema es
$f_{k-1}^{2}+2f_{k-1}f_{k}+f_{k}^{2}=\left(f_{k-1}+f_{k}\right)^{2}=f_{k+1}^{2}$
como queríamos mostrar. Entonces hay $f_{m}^{2}$ maneras de que los alumnos se redistribuyan perfectamente en los asientos de nuevo tras efectuar los movimientos permitidos.
Perdón, la suma arriba es
$2\sum_{s=0}^{k-1}{f_{s}^{2}}=2f_{k-1}f_{k}$.
Pues está fácil es Fibonacci. F(1)=1, F(2)=2, F(N)=F(N-1)+F(N-2). Demuestro la fórmula. Si los que están en la 1° columna intercambian lugares entre sí, hay F(N-1) posibilidades. Si no, digamos que el 1° de la 1° fila intercambia con el que está a su lado, entonces el 1° de la 2° fila también debe intercambiar con el que está a su lado entonces quedan F(N-2) maneras. Entonces para obtener una fórmula cerrada usa la de Fibonacci.
Perdón está mal eso.
Ahora sí va bien. Defino $f(n)$ la respuesta. Dibujamos una flecha de un cuadro al cuadro al que se fue ese alumno. Entonces si nos fijamos en el cuadro inferior izquierdo, es fácil ver que si seguimos las flechas vamos a terminar con un rectángulo. Entonces $f(n)=f(n-1)+2\left(f(n-2)+...+f(0)\right)+f(n-2)$. El $f(n-2)$ es para el caso en el que el de la esquina y el que está a su lado intercambian asientos, y el 2 es por si la dirección del rectángulo es en el sentido de las manecillas del reloj o no. Entonces vemos que $G^2$ funciona, con $G$ la secuencia Fibonaccio $G_0=G_1=1$. Si demostramos ésto, por la unicidad de la secuencia (pues $f(0)=1=f(1)=G_1=G_0$ y la recursión define la secuencia), habremos acabado. Demostremos que $G^2$ funciona. Queremos que:
$G_n^2=G_{n-1}^2+2\left(\displaystyle\sum_{i=0}^{n-2} G_i^2\right) + G_{n-2}^2$. Pero $G_n^2=G_{n-1}^2+G_{n-2}^2+2G_{n-1}G_{n-2}$. Así que queremos que $G_{n-1}G_{n-2}=\displaystyle\sum_{i=0}^{n-2} G_i^2$Ésto se ve trivialmente usando la fórmula recursiva e inducción. Quod erat demonstrandum. Respuesta: $f(n)=G_n^2$.$\clubsuit$.
¿Ya no se pueden eliminar comentarios?
Digamos que son $2$ filas y $m$ columnas, entonces a la fila de abajo se le asigna $1,2,\dots, m$ y a la de arriba $1+i,2+i,\dots,m+i$ de modo que los movimientos permitidos para un alumno es sumar $\pm 1$ ó $\pm i$. Pero si el alumno se encuentra en el número que tiene (originalmente el de su lugar), entonces la de todos los alumnos siempre es la misma, por lo que hay tantos $i$ como $-i$ y tantos $1$ como $-1$.
Si a un entero $n$ se le suma $1$ y a $n+1$ se le resta $1$, entonces: si a $n+1+i$ se le aumenta $1$, entonces todos los números con mayor norma no podrán tener norma menor o igual a $\sqrt{(n+1)^{2}+1}$ excepto por $n+2+i$ pero si a ése no se le resta $1$, en ese caso, tendremos a $2(m-n-1)+1$ estudiantes entre los $2(m-n-1)$ lugares y habría dos estudiantes en el mismo lugar así que no pasa. Por lo tanto a $n+2+i$ se le resta uno y entonces a estos dos se les puede aplicar el mismo razonamiento (sólo que ahora es la otra fila, pero es igual), y entonces todos están acomodados así conforme avanzamos en los enteros reales, pero obviamente no podremos terminar porque implicará que un estudiante no se moverá (pues es como llenar $2(m-n-1)+1$ lugares con fichas de área $2$). De modo que esto no puede pasar. Por lo tanto Si a un entero $n$ se le suma $1$ y a $n+1$ se le resta $1$, entonces $n+i$ y $n+i+1$ hacen lo mismo.
Otra situación con la que nos encontramos es cuando $n$ y $n+i$ intercambian lugares y es importante pues los que tienen mayor norma norma que $n$ no podrán tener menor que $n$ y viceversa.
Si nos fijamos en una persona, claramente, tomará el lugar de otra, y esta la de otra y así sucesivamente siguiento un camino (sumando y restando $1$'s e $i$'s) y si en algún momento regresamos a un punto por donde ya pasamos, y sucede por primera vez, entonces debe ser donde iniciamos, pues de lo contrario hubo dos personas que se movieron a ese lugar. Con esto, sabemos que todos los moviemientos son en un ciclo y más que eso, sabemos que si en un ciclo hay más de dos personas, no puede ser sólo horizontal o verticalmente, pues verticalmente sólo hay dos filas y horizontalmente si abarca, digamos, desde $n_{1}$ hasta $n_{2}\geq n_{1}+2$, entonces como es un ciclo y nos fijamos en el lugar $n_{1}$ como inicio, entonces al llegar a $n_{2}$ y tener que regresar a $n_{1}$, y no poder pasar por donde antes, deberá pasar por (desde) $n_{2}+i$ hasta $n_{1}+i$ y luego se le restará $i$ (no puede pasar por $n_{2}+1+i$ (y más allá) pues entonces no puede regresar a $n_{1}$ sin pasar por un lugar en el que ya estuvo (el camino), ni puede llegar a $n_{1}-1+i$ (y más allá) pues entonces la única forma de regresar y tocar el camino otra vez sólo en $n_{1}$ debe pasar por un entero real menos a $n_{1}$ y es contradcción a la suposición de que iba desde $n_{1}$ hasta $n_{2}$.
Así pues, estos son todos los tipos de movimientos. El primero, por su naturaleza, es equivalente a poner una pieza de $2\times 2$, el segundo de $2\times 1$ y el último de $2\times k$ con $m\geq k\geq 1$ (el caso particular en que $k=1$ es lo mismo que el movimiento dos). Ahora definamos a $g_{m}$ la cantidad de formas que se puede hacer el movimiento. Es fácil ver que en la primera columna tiene que haber movimiento, si es del primer tipo, entonces para el resto de los alumnos, hay $g_{m-2}$ formas de hacerlo, si es del tercer tipo, entonces hay (para la respectiva $k$), $2g_{m-k}$ formas de hacerlo para las demás (pues el ciclo puede fluir en cualquier dirección) excepto para $k=1$ en cuyo caso sólo es $g_{m-k}$. Es decir que $g_{m}=g_{m-2}+2\sum_{i=0}^{m-2}g_{i}+g_{m-1}$ dónde definimos de manera intuitiva que $g_{0}=1$ y $g_{1}=1$ pues sólo puede lograrse con el movimiento tres con $k=1$. Y con esta fórmula calculamos también $g_{2}=4$.
Ahora, con esta recursión rápidamente nos damos cuenta de que $g_{n+1}=2g_{n}+2g_{n-1}-g_{n-2}$. Esto es $f_{n+2}^{2}$ con $f_{n}$ el número de fibonacci $n$. Esto se debe a que los primeros tres valores coinciden (desfasados) y además $f_{n+2}^{2}=(f_{n+1}+f_{n})^{2}=f_{n+1}^{2}+f_{n}^{2}+2f_{n+1}f_{n}$ dónde $2f_{n+1}f_{n}=f_{n+1}(f_{n+1}-f_{n-1})+f_{n}(f_{n}+f_{n-1})=f_{n+1}^{2}+f_{n}^{2}-f_{n-1}(f_{n+1}-f_{n})=f_{n+1}^{2}+f_{n}^{2}-f_{n-1}^{2}$ y juntando ambas obtenemos la misma recursión, por lo que es cierto y acabamos.
después del "dónde" dice:
$2f_{n+1}f_{n}=f_{n+1}(f_{n+1}-f_{n-1})+f_{n}(f_{n}+f_{n-1}$ $=f_{n+1}^{2}+f_{n}^{2}-f_{n-1}(f_{n+1}-f_{n})$ $=f_{n+1}^{2}+f_{n}^{2}-f_{n-1}^{2}$
Sea $g(n)$ el numero de formas puede ocurrir este cambio para un tablero de $n\times 2$.
Para casos pequeños veamos que
$g(1)=1$, $g(2)=4$, $g(3)=9$.
Para $m \ge 3$, tomemos un tablero de $m\times 2$, de tal manera que al final del cambio también queda un alumno en cada asiento
Numeremos los asientos de la primera fila de izquierda a derecha con
$a_1, a_2, ... , a_m$, de igual manera numeramos los asientos de la segunda columna:
$b_1, b_2, ... , b_m$.
Caso 1.
si los alumno de la casillas $a_m$ y $b_m$ intercambian de lugar, entonces hay $g(m-1)$ formas de que los demás cambien de lugar.
Caso 2.
si los alumnos de $a_{m-1)$ y $a_m$ intercambian de lugar al igual que $b_{m-1)$ y $b_m$. Entonces hay $g(m-2)$ formas de que los demás cambien de lugar.
Caso 3.
si el alumno de $a_{m-1)$ se pasa a $a_m$, el de $a_m$ a $b_m$, entonces $b_m$ se pasa a $b_{m-1)$. De ahí o $b_{m-1)$ pasa a $a_{m-1)$, en cuyo caso tendríamos $g(m-2)$ formas de que los demás cambien de lugar, o $b_{m-1)$ pasa a $b_{m-2)$, entonces $a_{m-2)$ pasa a $a_{m-1)$, y volvemos a repetir el proceso de manera que al final nos queda que en el caso 3 hay
$g(m-2)+g(m-3)+...+g(1)$ formas de que los demás cambien de lugar.
Caso 4.
si el alumno de $b_{m-1)$ se pasa a $b_m$, el de $b_m$ a $a_m$. Que es anàlogo al caso anterior.
Por lo tanto
$g(m)=g(m-1)+g(m-2)+2\left(g(m-2)+...+g(1)\right)$
Ahora veamos que si $f_m$ es el m-esimo número en la sucesión de fibonacci.
$f_{m}^{2}=(f_{m-1}+f_{m-2})^{2}=f_{m-1}^{2}+f_{m-2}^{2}+2f_{m-1}f_{m-2}$
Además $f_{m-1}f_{m-2}=(f_{m-2}+f_{m-3})(f_{m-2})=f_{m-2}^{2}+f_{m-2}f_{m-3}$ que por un paso inductivo llegamos a que:
$f_{m-1}f_{m-2}=f_{m-2}^{2}+...+f_{1}^{2}$
Por lo tanto los cuadrados de la sucesión de fibonacci cumplen la misma recursión que la de la función que tomamos al principio, además comparten los primeros 3 términos. Por lo tanto
$g(m)=f_{m}^{2}$
Vemos el salón como un tablero de $mx2$.
Podemos ver los cambios de lugares como una permutación del conjunto, como es una permutación podemos verla como composición ciclos, dadas las condiciones del problema dichos ciclos deben de ser caminos cerrados moviéndose sobre casillas adyacentes sin repetir casilla, y para cada conjunto con más de dos casillas que representa un ciclo se puede transitar en dos direcciones.
Una permutación se dice buena si satisface las condiciones del problema.
Ahora, sea $C_n$ el número de veces que se puede hacer lo que buscamos contar en un tablero de $nx2$, ahora tomemos un tablero de de $(k+1)x2$, una permutación es $i$-buena si es buena y si existe un ciclo que usa al menos una casilla de la fila $k+1$ y una de las fila $k+1-i$, entonces $C_{k+1}=\sum_{i=1}^{k+1}{C_{k+1-i}t_i}$, ahora, haciendo un poco de análisis de casos vemos que $t_1=1$, $t_2=3$, $t_j=2$ para $j\geq 3$, substituyendo eso en la suma y haciendo un poco de álgebra podemos ver que $(C_{k+1}=2C_k+2C_{k-1}-C_{k-2}$, por inducción es fácil ver que los fibonaccis cumbplen pues $f_{n+1}^2=2f_n^2+2f_{n-1}^2-f_{n-2}^2$ es cierto si y solo si $2f_nf_{n-1}=f_{n}^2+f_{n-1}^2-f_{n-2}^2$ e igualando a cero y factorizando vemos que lo anterior es cierto si y solo si $0=f_{n-2}^2-f_{n-2}^2$.
Consideremos la multigráfica cuyos vértices son los asientos y donde dos vértices están unidos por una arista por cada niño que se desplace del uno al otro. Como todos los vértices tienen grado 2, es un hecho conocido que la gráfica está compuesta por la unión de ciclos ajenos. Ahora, numeremos los asientos $a_{1},a_{2},...,a_{m},b_{1},b_{2},...,b_{m}$ con $x_{i}$ y $y_{j}$ en la misma fila si $x$ es la misma letra que $y$ y ambos en la misma columna si $i=j$. Es evidente que los únicos ciclos posibles son cuando $a_{i}$ y $b_{i}$ intercambian alumnos (esto es, que el que estaba en $a_{i}$ se cambia a $b_{i}$ y el que estaba en $b_{i}$ se mueve a $a_{i}$), caso que denominaremos como ciclo A, cuando $a_{i},a_{i+1}$ o $b_{i},b_{i+i}$ con $i\in {1,2,...,m-1}$ intercambian alumnos, que llamaremos ciclo B, y cuando $a_{i}\rightarrow a_{i+1}\rightarrow...\rightarrow a_{i+k}\rightarrow$ $\rightarrow b_{i+k}\rightarrow b_{i+k-1}\rightarrow...\rightarrow b_{i}\rightarrow a_{i}$ o cuando sucede lo mismo cambiándole el sentido a todas las flechas (donde $x\rightarrow y$ significa que un alumno se mueve de $x$ a $y$). A estos últimos ciclos los llamaremos ciclos rectangulares $(i,i+k)$.
Sea $c(m)$ el número de cambios posibles para el acomodo de $m \times 2$.Como todo alumno se debe de mover, tenemos las siguientes opciones:
-Por $a_{m}$ pasa un ciclo A, luego hay $c(m-1)$ cambios posibles en el resto de los asientos.
-Por $a_{m}$ pasa un ciclo B, entonces por $b_{m}$ también, luego queda un acomodo de $m-2\times 2$ asientos, donde hay $c(m-2)$ cambios posibles.
-Por $a_{m}$ pasa un ciclo rectangular $(i,m)$. Entonces, queda un acomodo de $i-1\times 2$ asientos, y como el ciclo rectangular puede tener 2 sentidos, hay $2c(i-1)$ cambios posibles.
Como $i=1,2,...,m-1$, hay $2(c(m-2)+c(m-3)+...+c(2)+c(1)+1)$ maneras de hacer el cambio en este caso.
Entonces, $c(m)=c(m-1)+c(m-2)+2(c(m-2)+c(m-3)+...+c(1)+1)$. Es fácil ver que $c(1)=1$, $c(2)=4$. Demostraremos que $c(i)=f(i+1)^{2}$, donde $f(i)$ es el $i$-ésimo número de Fibonacci. Vemos que $f(2)^{2}=c(1)$ y que $f(3)^{2}=c(2)$. Basta ver que cumple la recursión, es decir, que
$f(m+1)^{2}=f(m)^{2}+f(m-1)^{2}+2(f(m-1)^{2}+f(m-2)^{2}+...+f(2)^{2}+f(1)^{2})$.
Tenemos que $f(m+1)^{2}=f(m)^{2}+f(m-1)^{2}+2f(m)f(m-1)$. Por otro lado, $f(m)f(m-1)=(f(m-1)+f(m-2))(f(m-2)+f(m-3))$ $=f(m-2)^{2}+f(m-1)(f(m-2)+f(m-3))+f(m-2)f(m-3)$ $=f(m-1)^{2}+f(m-2)^{2}+f(m-2)f(m-3)$. Por un argumento inductivo podemos demostrar que $f(i+1)f(i)=f(i)^{2}+f(i-1)^{2}+f(i-1)f(i-2)$. Entonces, $f(m)f(m-1)=f(m-1)^{2}+f(m-2)^{2}+...+f(2)^{2}+f(1)^{2}$, de donde $f(m+1)^{2}=f(m)^{2}+f(m-1)^{2}+2f(m-1)^{2}+f((m-2)^{2}+...+f(2)^{2}+f(1)^{2})$, como queríamos.
$h(m)$ es de cuantas maneras se puede dar este cambio con un acomodo de $m\times 2$ asientos.
Con casos pequeños vemos que $h(1)=1$, $h(2)=4$,
$h(3)=9$.
Vemos como se pueden mover las dos personas en la m-ésima fila.
Sea $a_i$ la persona en la primera columna, en la fila $i$, y sea $b_i$ la persona en la segunda columna, en la fila $i$.
Si $a_m$ y $b_m$ se sientan uno en el lugar del otro, entonces los demas se pueden reacomodar de $h_{m-1}$.
Ahora, si se cambian $a_{m-1}$ con $a_m$, y $b_{m-1}$ con $b_m$, entonces los demas se pueden acomodar de $h(m-2)$ maneras.
En un tercer caso, si $a_{m-1}$ se sienta en el lugar de $a_m$, $a_m$ en el lugar de $b_m$, y $b_m$ en el lugar de $b_{m-1}$, a partir de ahi, si los de la segunda columna se siguen pasando al lugar de enfrente, hasta que $b_k$ se pasa a $a_k$, entonces todas las $a_j$ con $j=\{k,(k+1),\dots ,m-2\}$ solo van a tener una opcion, que es sentarse en el lugar de $a_{j+1}$, y los demas tienen $h(k-1)$ maneras de acomodarse.
Asi en este caso hay $\sum_{i=1}^{m-2}{h(i)}$
Analogamente si en vez de moverse en sentido 'contrario a las manecillas del reloj', se mueven en sentido de las manecillas del reloj. Entonces tenemos que:
$h(m)=h(m-1)+h(m-2)+2\sum_{i=1}^{m-2}{h(i)}$
Ahora tomamos la sucesión de Fibonacci, con $f_0=f_1=1$, $f_2=2$, etc.
Veamos que $h(m)=(f_m)^2$
Los casos base ya estan en el comentario anterior.
$(f_m)^2=(f_{m-1}+f{m-2})^2=(f_{m-1})^2+(f{m-2})^2$
$+2f_{m-1}f_{m-2}=h(m-1)+h(m-2)+2f_{m-1}f_{m-2}$
Entonces para que se cumpla que $h(m)=(f_m)^2$, necesitamos que
$f_{m-1}f_{m-2}=\sum_{i=1}^{m-2}{h(i)}= \sum_{i=1}^{m-2}{(f_i)^2}$
$f_{m-1}f_{m-2}= (f_{m-2}+f_{m-3})f_{m-2}=(f_{m-2})^2+f_{m-2}f_{m-3}$
Y con otra induccion es facil ver que la igualdad que buscabamos es cierta.
$\boxed{h(m)=(f_m)^2}$
Publicar un comentario