P4 Un mago y sus fichas B/N

Dada una colección de varias fichas que pueden ser negras o blancas y que tienen, cada una, un número escrito en ellas, un mago hace el siguiente movimiento: Toca 2 de las fichas con distinto número y color, y la de número menor se convierte en una ficha idéntica a la otra. 

Sea $n$ un entero mayor o igual a 2. Para cada uno de los movimientos del 1 al $n$, el mago pone en la mesa una ficha negra o blanca con ese número. Luego hace su $movimiento$ para ir modificando la colección. 

A continuación, un ejemplo de dos movimientos realizados a una posible elección del mago con $n=5$, donde, para el primer movimiento, el mago escoge $1B$ y $3N$ y para el segundo $3N$ y $4B$:

$(1B, 2B, 3N, 4B, 5B) \rightarrow (3N, 2B, 3N, 4B, 5B) \rightarrow (4B, 2B, 3N, 4B, 5B)$ 

Sea $k$ el número total de movimientos que puede hacer el mago hasta que ya no puede (porque en su colección ya no tiene fichas de distinto color y número). Determina en términos de $n$, todos los posibles valores para $k$ (considerando las diferentes maneras en que el mago puede escoger los colores de las $n$ fichas al principio, y las distintas formas en que puede hacer sus movimientos).

Quisiera ver la solución

Enviado por GOLDEN NAC el 17 de Mayo de 2024 - 15:20.

Quisiera ver la solución

»

No encontré la solución

Enviado por Samuel Elias el 29 de Julio de 2025 - 16:23.

No encontré la solución oficial, la verdad no sé como haces la solución con combinatoria, pero aquí te va una solución con Gauss.

• Observa que cada ficha puede crear máximo $m-1$ movimientos, para $1 \leq m \leq n$ 
• Entonces, el total de movimientos máximo que se puede hacer es $\frac{n(n-1)}{2}$

Procedamos por inducción:

• Si $m=2$, la cantidad máxima de movimientos que se puede hacer es $\frac{2(2-1)}{2}=1$, lo cual se obtiene si ambas fichas son de distinto color.
• Si $m=n$, entonces la cantidad máxima de movimientos que se puede hacer es $\frac{m(m-1)}{2}$
• Si $m=n+1$, entonces basta que la ficha $n+1$ sea de diferente color que la $n$, y están alternando colores. De aquí, el número máximo de movimientos es $\frac{(n(n-1)}{2}+n+1=\frac{(n+1)(n)}{2}$ lo cual cumple la inducción.
• Para armar las demás respuestas, basta con acomodar las últimas $j$ fichas del mismo color, con $1 \leq j \leq n$

Por lo tanto, $0 \leq k \leq \frac{n(n-1)}{2}$.

»