El juego de los tres montones

[carroza]

Hola.

Querria compartir con vosotros un juego que aperndí hace muchos años:

Se parte de tres montoncitos de monedas, garbanzos, o lo que queramos. Hay dos jugadores, y en cada turno, cada uno retira todas las monedas que quiera (al menos una), de uno de los montoncitos. Pierde el que se vea obligado a retirar la ultima moneda.

El problema matemático consiste en determinar la estrategia optima (es decir, el numero de monedas que hay que retirar en nuestro turno), para ganar, es decir, para que el adversario se vea oblgado a retirar la ultima moneda. Pero antes de entrar en el problema matemático, vamos a jugar.

Un ejemplo: situación inicial: (3,2,1) monedas.

Jugador A : quita una moneda del tercer mntón. Quedan (3,2,0)

Jugador B: quita dos monedas del primer monton. Quedan (1,2,0)

Jugador A: quita dos monedas del segundo monton. Quedan (1,0,0)

Jugador B: se e obligado a coger la ultima moneda. B pierde y A gana.

Si os apetece jugar, os reto a una partida simultanea:

Situación inicial: (7,5,3). Es vuestro turno.


Saludos

[javisot20]

Pruebo a definir todas las combinaciones posibles suponiendo que inicies tú la partida o la inicie yo
( gracias por decir pocas cantidades de dinero jej)

Suponiendo que tengo la lista exacta de todas las combinaciones posibles iniciando yo la partida,
y tú tengas la lista exacta de todas las combinaciones posibles iniciando yo tambien la partida,

¿Que determina quien gana? Curioso problema, necesito tiempo y lo intento.

[carroza]

Con la posicion que he propuesto de partida, podrías ganar tu, si lo haces todo muy bien. Saludos

[Alriga]

Situación inicial: (7,5,3). Es vuestro turno

Uff, qué tiempos, a ver si me acuerdo:

(6, 5, 3)

Tu turno, saludos.

[carroza]

Bien jugado.
(453)

[Alriga]

(453)

(4, 5, 1)

Saludos.

[carroza]

Ok, Ariga. Veo que ya has jugado antes, y que me vas a ganar. Completemos el juego a beneficio de la audiencia
(4, 3 ,1)

[Alriga]

Sí, jugué hace muuchos años y conozco el mecanismo del juego:
(2, 3, 1)
Saludos.

[carroza]

Ok. si hago (1,3,1), alriga hace (1,1,1) y me gana. Si hago (2,2,1), alriga hace (2,2,0) y me gana. Y si hago (2,3,0), Alriga hace (2,2,0) y me gana.

[carroza]

Como Alriga me va a ganar en el ejemplo anterior, voy a proponer otro caso de números más grandes. Contestad si quereis en comentarios, para no alargar el hilo.
(34, 15, 6)

[Abdulai]

Yo también conozco una estrategia para este juego, aplicable a cualquier número de montones. Después estaría bueno ver si todos usamos la misma.
(acá jugaría (9,15,6) )

[carroza]

Ok. Comparto la estrategia que acabo de deducir, para compararlas con las de Abdulai y Alriga. Lo pongo oculto, en el entorno solucion, para no destripar el juego a los que quieran practicarlo

Solución: 

- Se escriben los numeros de los montones en binario. Para el caso (34, 15, 6), sería (100010, 1111, 110)

- Ahora se comparan los digitos correspondientes a las diferentes posiciones de "unidades", "centenas", "decenas", etc. La finalidad es jugar dejando al oponente tres numeros tales que, en binario, hayan cero o dos digitos "1" en cada una de las posiciones. En este caso, ya hay diferencias en el digito sexto, es decir las "centenas de millar", debido al primer numero. Ese primer numero (34 en decimal, 100010 en binario) es el que hay que cambiar.

-el numero que hay que cambiar hay que reducirlo, para obtener uno que cumpla el criterio anterior. Este debe ser 1001, ya que el conjunto (1001, 1111, 110) tiene dos "1" en cada una de las posiciones. Por tanto, nuestra jugada, en decimal, debe ser (9,15,6).

- Nuestro oponente, en su jugada, debe alterar la condicion que fijamos de cero o dos "1" en cada posicion. Por ello, en nuestro turno, reimponemos la condicion. Esto nos lleva indefectiblemente a la victoria.

- A partir del comentario de Adulai, me he dado cuenta de que es facil ampliar este criterio para que sea valido para un numero arbitrario de montones, no tres. Simplemente, exigimos que , tras nuestra jugada, haya un numero par de "1" en cada posicion.

- Hay excepciones a esta regla con las jugadas en las que solo hay ceros y unos. Por ejemplo, (0,0,1) es ganadora, (0,1,1) es perdedora, (1,1,1,) es ganadora. Pero estos casos son triviales.

Saludos

[Alriga]

Solución: 

Yo como Abdulai, conocía el juego con un numero arbitrario de montones con un número arbitrario de unidades en cada montón. El juego lo conocí hace 3 ó 4 décadas en alguno de los muchos libros de matemáticas divulgativas/recreativas de los que tengo, pero no recuerdo en cual, ¿Martin Gardner, Ian Stewart, Adrián Paenza, Yakov Perelman,...?

Hago lo mismo que carroza , expreso en binario la cantidad de cada montón. Por ejemplo inicio (34, 15, 6)

100010 = 34
__1111 = 15
___110 = 6

101231 (suma de columnas)

Sumo cada columna en decimal, obtengo 101231. Busco quitar unidades de uno de los montones para que la nueva suma de columnas tenga todas las cifras pares. Ello se consigue convirtiendo la primera fila en 1001

1001 = 9
1111 = 15
_110 = 6

2222 (suma de columnas)

La jugada ganadora es convertir 100010=34 en 1001=9

Solución (9, 15, 6)

Últimamente en un programa diario de entretenimiento que se llama "El Hormiguero" que emiten en un canal de televisión español, de vez en cuando retan al invitado del día a jugar este juego: me da un poco de rabia verlo, porque "pintan" al jugador de El Hormiguero como una especie de genio "campeón mundial", cuando en el fondo lo que está haciendo es implementar un sencillo algoritmo.

Saludos.

[Abdulai]

Solución: 

Veo que los tres aplicamos el mismo sistema

Yo lo conocí leyendo sobre grafos aplicados a la teoría de juegos.
La idea en estos juegos de dos personas es construir un grafo donde cada nodo se corresponda a una posición y separar dos grupos G y P.
En G (Ganador) no hay nodos conectados entre si, mientras que en P (Perdedor) si pueden estarlo pero cada nodo está conectado el menos a uno de G.

De esta manera, si uno está en G no le queda otra opción que ir a P, y estando en P siempre se puede volver a G.
luego de un juego ejemplo que no me acuerdo se pasaba al caso donde las posiciones fueran tantas que no fuera nada práctico dibujar el grafo. Y es el caso de este juego...

El lugar de dibujar se construye una función de posición F(pos) completamente arbitraria con las mismas propiedades que el grafo: Desde un valor de F(pos) en el conjunto ganador es imposible pasar a otro y desde un valor F(pos) en conjunto perdedor se puede pasar a un F(pos) ganador.

Acá la función es la paridad entre columnas binarias, si todas son par, alterando una fila es imposible que siga siendo par, y a si hay algunas impares, alterando una siempre se vuelve a dejarlas pares.

Si esto lo hiciéramos mediante un programa, y N1 fuesen los elementos de la fila mayor, bastaría hacer un XOR con el resto de las filas dejando N1 = N2 XOR N3 XOR N4 XOR ... (XOR es la función OR-exclusiva)
No necesariamente se debe modificar la mayor, pero con las otra no siempre se puede.

Donde leí esto las reglas no eran las mismas, quien ganaba era quien retiraba el último montón.
Si quien pierde es quien retira la última, el procedimiento es el mismo salvo cuando queda un elemento en cada fila, ahi la paridad debe ser impar.


Hace años en un programa de televisión usaron este juego y el ganador se llevaba un premio $$$ interesante.
Después de unos meses donde no podía creer que nadie dentro del equipo de producción supiera que esto admitía una estrategia ganadora, apareció el conductor explicando una carta que había recibido, mas o menos dijo:
"Nos llegó una carta del departamento de Matemáticas de la universidad bla bla bla explicando que este juego no debía utilizarse porque aplicando esta estrategia un jugador puede ganar siempre. A continuación no explican detallamente la estrategia.
Ninguno de nosotros entendió NADA, pero por las dudas, retiramos el juego."

[Jaime Rudas]

El juego lo conocí hace 3 ó 4 décadas en alguno de los muchos libros de matemáticas divulgativas/recreativas de los que tengo, pero no recuerdo en cual, ¿Martin Gardner, Ian Stewart, Adrián Paenza, Yakov Perelman,...?

A mí me pasó exactamente lo mismo y estoy casi seguro que fue en un libro de Martin Gardner. Recuerdo también que Gardner mencionaba que la estrategia la había deducido un matemático estadounidense a principios del siglo pasado. No logré encontrar la referencia de Gardner pero, después de mucho buscar, encontré el nombre del matemático y el artículo que escribió sobre el tema en una revista de prestigio. También me enteré que le había puesto un nombre al juego.

Aunque no es precisamente un problema de ingenio, ¿alguien se anima a averiguar estos tres datos?

[Richard R Richard]

Yo no participe del hilo porque conocía la respuesta a un juego similar de varios montones, en ese juego como en este el que empieza pierde si el.co trinchante sabe que jugar en respuesta a la movida.

[Abdulai]

Yo no participe del hilo porque conocía la respuesta a un juego similar de varios montones, en ese juego como en este el que empieza pierde si el.co trinchante sabe que jugar en respuesta a la movida.

Al menos en este, si la paridad de todas las columnas es par, pierde quien empieza, caso contrario, el mas común, gana siempre. Si conoce la estrategia, claro

[javisot20]

Sabemos que si cada montón ( de lo que sea ) tuviese solo 1 elemento, este juego lo gana quién comience la partida en función del número de montones.

-Si tenemos A y B quién comienza primero gana.
-Si tenemos A, B, C quién comienza primero pierde.
-A,B,C,D quién comienza primero gana.

Etc


Ahora supongamos que tenemos A y B, pero A tiene 1 elemento más que B.

Entonces aparecen dos posibilidades que equivalen a un juego lineal de montones con un único elemento.

Ya que podemos comenzar jugando los 2 elementos de A como si fuese un único elemento y perder el contrario,o podemos jugar A,B,C al separar los elementos de A, haciendo un nuevo montón unitario C,
lo que en este caso nos haría perder.



Estaba extendiéndolo con otro enfoque para ver a donde llego por mi cuenta.
¿ Sobre este inicio puedo intentar seguir o tiene algún error que no veo ?


Me gustó lo que comentó Abdulai, eso fue lo primero que pensé, pero claro...depende de la capacidad computacional. ( en mi caso del lapiz, papel , tiempo y paciencia disponible )

[Richard R Richard]

Solución: 

Al menos en este, si la paridad de todas las columnas es par, pierde quien empieza, caso contrario, el mas común, gana siempre. Si conoce la estrategia, claro

Oh oh o eso quien empieza gana, .. si ambos conocen la estrategia el que empieza gana.
El número de montones con una unica pieza debe ser par , el número de momtones con más de una pieza tiene que ser par.
En la version que conozco incluso se podía siempre extraer una pieza del montón y dejar incluso dividir el montón en dos montones más pequeños de similar número final de piezas.