Optimizar una estrategia ganadora para un juego de mesa rápido

Question

Un amigo mío recientemente compartió el siguiente rompecabezas conmigo:

Rompecabezas: Una circular en la mesa se divide en cuatro congruentes cuadrantes por dos líneas perpendiculares. (Piense en un círculo en el $xy$-plano centrado en el origen y se divide en cuadrantes por los ejes de coordenadas.) En cada cuadrante está a un cuarto cubierto por un revés opaco de la copa. Las tazas son idénticos en apariencia como son sus posiciones relativas en cada uno de los cuadrantes. Un "movimiento" consiste en la extracción de cualquiera de las dos tazas y, a continuación, cambiar las orientaciones (heads up\colas) de ninguno, uno o ambos de los correspondientes monedas. Después de la mudanza que usted gire su espalda y un juez inspecciona las monedas debajo de los otros dos tazas. "Ganar" si todas las cuatro monedas están orientados de la misma, ya sea a todos los jefes, o de todas las colas. Si usted no gana en un movimiento, el juez sustituye las copas de nuevo en su forma original (indistinguibles) posiciones sobre el (actualmente orientado a) monedas y da la plataforma giratoria spin. Cuando deja de girar girar alrededor de la espalda y se permite otro movimiento. Demostrar que se puede ganar en la mayoría de los cinco movimientos.

Después de que jugando un poco con este rompecabezas para un poco, yo era capaz de llegar con tres soluciones diferentes, todos los cuales participan 5 se mueve. (Mi amigo tenía originalmente una solución con 6 movimientos, pero mejoró a 5, por lo tanto, el requisito de encontrar una solución que involucre a la mayoría de los movimientos 5.)

Pregunta: Es posible garantizar una solución con sólo 4 se mueve? O un inteligente (es decir, no la fuerza bruta) prueba que demuestra movimientos 5 es el menor número de movimientos que garantizan una ganancia?

Answer 1

Aquí es una prueba de que $5$ es el mínimo:

En primer lugar, cada vez se compone de dos "movimientos": una 'elección-move', que es donde usted elegir el que dos tazas de quitar, y un "flip-move', donde voltear a cualquiera de las monedas que se llega a ver.

Segundo, tenga en cuenta que sólo hay dos posibles 'elección-se mueve': elija dos adyacentes tazas o junto a dos tazas ... y es evidente a partir de la instalación que no importa cual de los cuatro pares adyacentes o cual de los dos pares opuestos.

Tercero, sólo hay tres tipos de monedas, las configuraciones en las que no todos los cuatro monedas de la cara de la misma manera:

A. tres monedas en la cara de la misma manera

B. dos monedas adyacentes de la cara de la misma manera

C. dos opuestos monedas cara de la misma manera

Usted puede estar en uno de varios estados que, como veremos, aparecen aquí de "mejor" a "peor":

1. Usted sabe que usted está en la situación C

2. Usted sabe que usted está en la situación B

3. Usted sabe que usted está en Una situación

4. Usted sabe que dos monedas de la cara de la misma manera, pero no sabemos si es B o C

5. Usted no sabe si usted está en la situación a, B, o C

Vamos a considerar estos, con el fin de "mejor" a "peor":

1. si usted sabe que usted está en la situación C, entonces la estrategia óptima es, por supuesto, a elegir dos opuestos monedas y vuelta, y así terminar el juego (y que, obviamente, no puede hacer nada mejor que eso)

2. Si usted sabe que usted está en la situación B, entonces la estrategia óptima es elegir dos monedas adyacentes: si son los mismos, voltear a ambos, y que va a terminar el juego, y si no son el mismo, luego voltear a ambos a conseguir en la situación C, y terminar el juego después de eso. Está claro que esta es la mejor estrategia para el estado 2, desde la elección de dos opuestos monedas (que se han opuesto a los lados) y luego voltear no o dos monedas le hará permanecer en el estado 2, y mover de un tirón de la moneda de 1 hace que vaya al estado 1, que, como veremos, es aún peor.

3. Si usted sabe que usted está en la situación a, entonces la estrategia óptima es elegir dos opuestos monedas. Si por casualidad usted conoce de qué lado es que es el impar hacia fuera, luego si veo que uno, se da la vuelta y va a ganar (claramente no se puede hacer mejor). Si usted ve a dos de las mismas caras, luego voltear una de las monedas, que se obtiene en el estado 2 (no se puede hacer mejor, ya que voltear ninguno o ambos se mantienen en estado 1), y por lo tanto dos movimientos de terminar el juego. La elección de dos monedas adyacentes no es una buena estrategia cuando en el estado 1, ya que podría llegar a ver dos monedas que se enfrentan de la misma manera, y por lo tanto voltear ninguno o ambos mantiene en el estado 1, y puesto que no sabes donde lo extraño se encuentra, volteo la moneda llega hasta el estado 4 que, como veremos, tiene un escenario del peor caso de ser 3 movimientos de terminar el juego. En otras palabras, la mejor estrategia cuando en el estado 3 es elegir opuesta de la moneda, que con un óptimo sistema de juego-el juego tiene un peor caso de terminar el juego en 3 movimientos.

4. Si usted sabe que las monedas que se encuentran en la configuración B, o C, pero no sabe que uno, entonces la estrategia óptima es elegir junto a dos tazas, desde la elección de al lado dos tazas podría revelar dos monedas que no se enfrentan de la misma manera, lo que sería compatible con B y C, y para que no te dice nada. Ahora, si los dos opuestos monedas muestran la misma cara, entonces usted está claramente en la situación C, de modo flip tanto para terminar el juego. Si el contrario monedas muestran diferentes caras, sin embargo, usted sabe que usted está en la situación B, pero lanzar cualquier monedas no mejora su estado, lo que significa que puede mover en el estado 2, y terminar el juego en la mayoría de los 2 movimientos. Por lo tanto, en el peor de los casos, tomará de 3 movimientos para terminar el juego cuando en el estado 4.

5. Finalmente, en el comienzo del juego se encuentra en el estado 5. Ahora usted puede terminar el juego en la mayoría de los 5 movimientos de la siguiente forma: seleccione al lado dos tazas, asegúrese de que ambas monedas son los jefes, y, a continuación, en el siguiente turno de elegir junto a dos tazas, y de nuevo, asegúrese de que ambas monedas son los jefes. Esto asegurará que yo he volteado exactamente tres monedas a los jefes, y por lo tanto de que usted está en el estado 3 si no has acabado el juego ya. Y, como vimos, se toma en el peor de los 3 más movimientos para terminar el juego.

Observe que usted podría, por supuesto, han hecho que las tres monedas colas, y usted también puede elegir dos opuestos monedas y, a continuación, elija monedas adyacentes.... aunque para una estrategia óptima que minimiza el esperado número de vueltas, primero debe elegir dos adyacentes tazas, y luego recoger junto a dos tazas, por si el contrario tazas de mostrar la misma cara, entonces usted puede voltear uno de ellos para asegurarse de llegar a la configuración de la B.

OK, pero ¿por qué no puedes hacerlo mejor, empezando por el principio del juego? Bueno, después de un turno que no han visto a dos de las monedas, y por lo tanto no se puede saber si usted está en la situación a, B, o C.

Por otra parte, es imposible llegar a cualquiera de estado de 1 o de 2 en 2 se mueve desde el inicio:

Primero de todo, si usted hace la misma 'elección-mover" para los dos primeros se mueve, entonces es posible ver el mismo dos monedas de dos veces, lo que significa que usted no sabe nada acerca de los otros dos monedas, excepto que, dado que las dos monedas que usted vio cara de la misma manera, las otras dos monedas no son tanto también hacia de esa manera. Por lo tanto, usted no sabe si uno de los dos de los otros dos monedas frente a la otra manera, y por lo tanto usted no puede conseguir a estado 1 o 2 de esa manera.

Sin embargo, si usted hace dos diferentes 'elección-se mueve' para los dos primeros movimientos, entonces usted está garantizado para ver exactamente tres monedas diferentes, lo que significa que usted no conoce la orientación de la cuarta moneda (y, por tanto, de nuevo no se puede llegar al estado 1 o 2), a menos que usted ha hecho todas las 3 monedas en la cara de la misma manera ... que es exactamente lo que dijo que era la mejor estrategia, y que conduce a un peor de los casos, de 5 de movimientos.