Lanzando monedas en un círculo

Question

Tenemos un conjunto de N monedas que se colocan en un círculo. Todos tienen "Colas" boca arriba. Las monedas son todas distintas y tienen números (1,2,3 ... N) escritos en ellas.

En cada movimiento, lanzamos 3 monedas consecutivas. Es decir, considere:

HHHTT

Si decido lanzar las monedas 3, 4 y 5, obtendré: HHTHH

Ahora, puede haber 2 ^ N permutaciones distintas de cara y cruz de N monedas distintas.

1.Probar / refutar que hay un conjunto finito de movimientos en los que podemos alcanzar cualquiera de las (2 ^ N) permutación cara-cruz de estas N monedas, desde la permutación inicial de todas cruces.

Además, si es posible alcanzar cualquier permutación, entonces cuál es el número máximo de movimientos que se necesitan para llegar a cualquier permutación desde la permutación inicial de todas las colas.

Para mayor aclaración, si N fuera 3, por ejemplo, las 2 ^ 3 permutaciones distintas de estas 3 monedas serían:

TTT

TTH

THT

THH

HHH

HHT

HTH

HTT

Answer 1

Asumamos $N \geq 3$o el problema no está bien definido.

Parte 1:

La posición final de una moneda depende solo de cuántas veces se haya lanzado (número par de lanzamientos, será T; número impar, H).

Entonces, los movimientos (que constan de tres giros) son conmutativos. Además, los movimientos son claramente autoinversos, por lo que no tiene sentido hacer el mismo movimiento dos veces. Por lo tanto, debemos preocuparnos solo por conjuntos (desordenados) de posiciones de movimiento (de los cuales también hay$2^N$).

Si no se pueden alcanzar todas las posiciones, entonces dos conjuntos de movimientos diferentes deben dar el mismo resultado. Pero eso significa que la diferencia simétrica (XOR) entre estos conjuntos de movimientos debe dar la configuración con todo T. Así que en su lugar podemos preguntar si hay algún conjunto de movimientos no vacío que dé todo T.

Para cualquier conjunto de movimientos, cada moneda será lanzada entre 0 y 3 veces. Además, el número de lanzamientos de monedas adyacentes debe diferir solo en 0 o 1. (Solo hay un movimiento que$x$ y no $x + 1$y viceversa.) Entonces, para obtener todo T, el número de lanzamientos debe ser todos 0 o todos 2. Todo 0 solo es posible con el juego de movimientos vacío. ¿Qué pasa con los 2?

El número total de lanzamientos debe ser un múltiplo de 3 porque cada movimiento arroja tres monedas. Entonces, es imposible obtener los 2 a menos que$N$ es un múltiplo de 3. Si $N$es un múltiplo de 3, es fácil. Cada moneda se puede lanzar moviéndose en una de cada tres posiciones. Luego, podemos hacer lo mismo de nuevo, pero cambiamos en 1 para darles la vuelta.

Por lo tanto, cada posición final es accesible si y solo si$N$no es divisible por 3.

Parte 2:

Si cada posición es alcanzable, entonces cada conjunto de movimientos alcanza una posición diferente. En particular, el conjunto de todas las posiciones de movimiento alcanza una determinada posición final en$N$movimientos, y ninguna otra posición requerirá más que muchos movimientos. Esta posición en particular es en realidad toda H, ya que lanzará cada moneda 3 veces.

Para calcular rápidamente el conjunto de movimientos para una posición final determinada, sugeriría calcular primero el conjunto de movimientos que arroja la moneda 1. Luego, sabremos cómo lanzar cualquier moneda cambiando este conjunto de movimientos. Y luego podemos calcular cualquier resultado combinando conjuntos de movimientos de una sola moneda (con diferencia simétrica / XOR).

Answer 2

Enfoque menos "mathy":

Es obvio que el problema para llegar a una configuración arbitraria es equivalente a un conjunto de movimientos que lanza exactamente una moneda.

Ahora, como encontrarlo:

Puede construir fácilmente la secuencia de lanzamiento requerida utilizando la secuencia 1,2,4,5,7, ... (los números corresponden a la moneda inicial, 1 significa lanzar monedas 1,2,3). Esto lanzará la moneda 2 (N = 3k + 1) o N (N = 3k + 2). La construcción es obvia, comience con la moneda 1 que está colocando como cara con el primer movimiento, siga lanzando el resto para que solo haya 1-2 caras propagándose hacia el "final" del círculo. Una vez que esas cabezas (casi) se encuentren con la primera, realice el giro final. Con N = 3k + 1 obtienes una cara al final y terminas lanzando solo la moneda 2, con N = 3k + 2 obtienes una cara 1 antes del final y lanzas solo la moneda N. Con N = 3k obtienes 2 monedas en al final y llegar a todas las colas. Debido a que no puede "exprimir" esas monedas para quedarse con una sola "cara", no es posible alcanzar todas las configuraciones.

Ahora en el peor de los casos:

Para obtener todas las caras, es necesario que todas las monedas sean lanzadas 1 o 3 veces. Obviamente, no se puede hacer que todas las monedas se lancen 1 vez con N = 3k + 1 o 2. Si una moneda X se lanza 3 veces, la moneda X + 1 ya se lanzó 2 veces y necesita ser lanzada una vez más, etc. debe lanzar todas las monedas 3 veces para obtener todas las caras de las iniciales de todas las cruces.