Let $n \ge 2$ be a positive integer. For every number from $1$ to $n$, there is a card with this number and which is either black or white. A magician can repeatedly perform the following move: For any two tiles with different number and different colour, he can replace the card with the smaller number by one identical to the other card. For instance, when $n=5$ and the initial configuration is $(1B, 2B, 3W, 4B,5B)$, the magician can choose $1B, 3W$ on the first move to obtain $(3W, 2B, 3W, 4B, 5B)$ and then $3W, 4B$ on the second move to obtain $(4B, 2B, 3W, 4B, 5B)$. Determine in terms of $n$ all possible lengths of sequences of moves from any possible initial configuration to any configuration in which no more move is possible.
Problem
Source: Mexico 2023/4
Tags: combinatorics, combinatorics proposed, Magician
13.04.2024 22:06
¿No hay alguna solución aún? me gustaría verla.Este problemas es feo...
23.04.2024 22:09
Para cualquier movimiento se reemplaza una ficha por otra y viceversa, cada ficha puede reemplazar solo m-1 fichas (con m el número de la ficha ya que puede cambiar a otros por el solo si son menores, y solo hay m-1 números menores a el), si sumamos todas los movimientos de las fichas tenemos n(n-1)/2 movimientos, esta cantidad de movimientos solo es obtenible si la configuración inicial es 1B, 2W, 3B, 4W.... Así o cambiando los B por W y viceversa, pues si cambiamos los 1 por los 2, los 2 por los 3...... Habremos hecho todos los movimientos posibles. Como mínimo habrán 0 (si todos son del mismo color), y para obtener cualquier valor intermedio solo hay que identificar como se puede escribir como suma de distintos enteros positivos menores a n, entonces del uno al s-1 (con s el número de la primera carta a sumar) será del color W, luego del s al p (la segunda carta a sumar) del color B y así.
03.08.2024 15:41
Entonces,¿Los valores posibles para k son todos los de 0 al n(n-1)/2?
19.09.2024 07:58
Hola, soy nuevo, parece que no puedo escribir en Latex pero intentaré hacerlo lo más claro posible. Los posibles valores son 0,1,2,...,(n-1)n/2. Es claro que 0 es una posibilidad, pues podemos empezar con todas las cartas del mismo color. Para ver que n(n-1)/2 es posible, tomemos la configuración inicial en la que los números en orden están coloreados de manera alternada. La carta 1 la cambiamos por la 2. Ahora las 2 cartas de 2 las cambiamos por el 3; las 3 cartas de 3 la cambiamos por el 4 y así sucesivamente, hasta obtener (n-1) cartas con el número (n-1); cambiamos estas (n-1) cartas por n. Hemos realizado en este proceso exactamente 1+2+3+...+(n-1)=(n-1)n/2 movimientos. Veamos que de hecho es la máxima cantidad de movimientos que podemos hacer antes de obtener una configuración en la que no podemos hacer nada más. Se considera la suma de todas las cartas en cada paso; la suma inicial es 1+2+...+n=n(n+1)/2. En cada paso la suma incrementa en al menos una unidad. Como la máxima suma que podemos obtener es n^2 (cuando todas las cartas tienen valor n), entonces no podemos realizar más de n^2-n(n+1)/2=n(n-1)/2 movimientos. Observe que este proceso de (n-1)n/2 movimientos lo podemos realizar independientemente de si los números son 1,2,...,n. Lo podemos hacer con cartas que tengan n posibles valores (nos referiremos a este como el caso generalizado). Probaremos ahora que el proceso se puede realizar en exactamente k movimientos para cada k en S_{n}={1,2,...,(n-1)n/2}. Para cada entero positivo n≥2, sea f(n)=1+2+...+(n-1)=(n-1)n/2. A partir de aquí consideraremos el caso generalizado (con n números distintos en lugar de los números del 1 al n). Probaremos por inducción en n que existe una configuración inicial en la que podemos realizar exactamente k movimientos para cada k en S_{n} y además dejar todas las cartas de color negro. El caso base n=2 es trivial, pues si iniciamos con la configuración (a_1W, a_2B) con a_1<a_2 hacemos un sólo movimiento y dejamos todas las cartas de color negro. Supongamos que para cierta n≥2 podemos hacer el proceso en exactamente k movimientos para cada k en {1,2,...,(n-1)n/2} y obtener puras cartas de color negro. Veamos el resultado para n+1. Separamos la carta con el número mayor a_{n+1} y nos fijamos en las demás. Por hipótesis de inducción existe una configuración de las n cartas restantes que deja todas estas cartas de negro en exactamente k movimientos para cada k en S_n. Entonces, es claro que si dejamos la carta mayor de negro, podemos elegir un configuración adecuada de las demás cartas para realizar exactamente k movimientos para dejar las n+1 cartas de negro para cada k en S_n. Para finalizar, consideremos nuevamente los números de las cartas en orden ascendente a_1<a_2<...<a_n<a_{n+1}. Tomamos la t-ésima carta para t en {1,2,...,n} y la separamos del resto. Podemos colorear las demás cartas de forma alternada de manera que la última carta a_{n+1} sea negra. La carta que separamos la coloreamos de color diferente a la (t+1)-ésima carta. Entonces esta carta a_t la podemos cambiar a a_{t+1}, luego a a_{t+2} y así sucesivamente hasta cambiarla por la carta a_{n+1}. Hemos realizado en este momento (n+1-t) movimientos. Si separamos nuevamente esta carta, las demás cartas están coloreadas de manera alternada en orden ascendente, de modo que igual que al principio, podemos realizar el mismo proceso para dejar todas las demás cartas iguales a la última carta (que está pintada de negro). Es claro que hemos usado exactamente (n+1-t)+f(n) movimientos. Como t puede variar entre 1 y n, entonces también podemos realizar el proceso en exactamente k movimientos para cada k en {f(n)+1, f(n)+2, ... , f(n)+n} movimientos. Como S_{n+1} = {1,2, ... ,(n-1)n/2, f(n)+1, ... , f(n)+n}, hemos terminado.