Masticar

Chomp es un juego de estrategia para dos jugadores que se juega en una cuadrícula rectangular formada por celdas cuadradas más pequeñas , que pueden imaginarse como los bloques de una barra de chocolate . Los jugadores se turnan para elegir un bloque y "comerlo" (retirarlo del tablero), junto con los que están debajo y a su derecha. El bloque superior izquierdo está "envenenado" y el jugador que se lo come pierde.

La formulación de Chomp mediante barras de chocolate se debe a David Gale , pero Frederik Schuh publicó anteriormente un juego equivalente expresado en términos de elegir divisores de un número entero fijo .

Chomp es un caso especial de juego de poset en el que el conjunto parcialmente ordenado sobre el que se juega es un producto de órdenes totales con el elemento mínimo (bloque venenoso) eliminado.

A continuación se muestra la secuencia de movimientos en una partida típica que comienza con una barra de 4 × 5:

El jugador A come dos bloques de la esquina inferior derecha; el jugador B come tres de la fila inferior; el jugador A elige el bloque a la derecha del bloque envenenado y come once bloques; el jugador B come tres bloques de la columna restante, dejando solo el bloque envenenado. El jugador A debe comerse el último bloque y, por lo tanto, pierde.

Tenga en cuenta que, puesto que es demostrable que el jugador A puede ganar cuando comienza con una barra de 4 × 5, al menos uno de los movimientos de A es un error.

Las posiciones intermedias en un Chomp m × n son particiones de enteros (secuencias no crecientes de enteros positivos) λ ₁ ≥ λ ₂ ≥···≥ λ _r , con λ ₁ ≤ n y r ≤ m . Su número es el coeficiente binomial${\displaystyle {\binom {m+n}{n}}}$, que crece exponencialmente con m y n . ^{[ 1 ]}

Chomp pertenece a la categoría de juegos imparciales de información perfecta para dos jugadores , lo que hace que también sea analizable por Nim debido al teorema de Sprague-Grundy .

Para cualquier posición inicial rectangular, excepto 1×1, el primer jugador puede ganar. Esto se puede demostrar mediante un argumento de robo de estrategia : supongamos que el segundo jugador tiene una estrategia ganadora contra cualquier movimiento inicial del primer jugador. Supongamos entonces que el primer jugador solo toma la casilla inferior derecha. Según nuestra suposición, el segundo jugador tiene una respuesta que le aseguraría la victoria. Pero si existe tal respuesta ganadora, el primer jugador podría haberla jugado en su primer movimiento y, por lo tanto, haber forzado la victoria. Por consiguiente, el segundo jugador no puede tener una estrategia ganadora.

Los ordenadores pueden calcular fácilmente las jugadas ganadoras de este juego en tableros bidimensionales de tamaño razonable. Sin embargo, dado que el número de posiciones crece exponencialmente, esto resulta inviable para tableros más grandes.

Partiendo de una cuadrícula cuadrada (es decir, n × n para cualquier n ≥ 2), la estrategia ganadora se puede expresar fácilmente. El primer jugador debe presentar al segundo una figura en forma de L de una sola fila y una sola columna, de la misma longitud, conectadas en la casilla venenosa. A continuación, cualquier movimiento que realice el segundo jugador en uno de los brazos de la L , el primer jugador responde con el mismo movimiento en el otro brazo, presentando siempre al segundo jugador una figura en forma de L simétrica . Finalmente, esta L se reducirá a la casilla venenosa, y el segundo jugador perderá.

De forma similar, cualquier n × 2 (para cualquier n ≥ 2) también es trivial. El movimiento inicial ganador siempre es la casilla inferior derecha. El tablero después de este movimiento puede considerarse como dos cadenas verticales de casillas (ignorando la casilla envenenada), y para ganar, basta con imitar los movimientos del jugador 2 en la otra cadena. Sin embargo, otras vías hacia la victoria suelen ser más complicadas.

El juego Chomp tridimensional comienza con una barra de chocolate formada por un cuboide de bloques indexados como (i,j,k). Un movimiento consiste en tomar un bloque junto con cualquier otro cuyos índices sean todos mayores o iguales al índice correspondiente del bloque elegido. De la misma manera, Chomp puede generalizarse a cualquier número de dimensiones.

Chomp a veces se describe numéricamente. Se da un número natural inicial , y los jugadores se turnan para elegir divisores positivos de dicho número, pero no pueden elegir 1 ni un múltiplo de un divisor elegido previamente. Este juego modela Chomp n- dimensional , donde el número natural inicial tiene n factores primos y las dimensiones del tablero de Chomp están dadas por los exponentes de los primos en su factorización prima . Chomp ordinal se juega en un tablero infinito con algunas de sus dimensiones siendo números ordinales : por ejemplo, una barra de 2 × (ω + 4). Un movimiento consiste en elegir cualquier bloque y eliminar todos los bloques cuyos índices sean mayores o iguales a los índices correspondientes del bloque elegido. El caso de Chomp ω × ω × ω es un problema abierto notable; se ha ofrecido una recompensa de $100 ^{[ 2 ]} por encontrar un primer movimiento ganador.

En términos generales, Chomp se puede jugar sobre cualquier conjunto parcialmente ordenado con un elemento mínimo . Un movimiento consiste en eliminar cualquier elemento junto con todos los elementos mayores. Un jugador pierde al tomar el elemento mínimo.

Todas las variantes de Chomp también pueden jugarse sin recurrir al veneno, utilizando la convención de juego misère : el jugador que come el último bloque de chocolate no se envenena, sino que simplemente pierde por ser el último jugador. Esto es idéntico a la regla habitual al jugar Chomp solo, pero difiere al jugar la suma disyuntiva de partidas de Chomp, donde solo el último bloque de chocolate resulta perdedor.

• Nim
• Hackenbush

• Zeilberger, Doron (2004). "Chomp, recurrencias y caos(?)". J. Diff. Eq. Applic . 10 ( 13–15 ): 1281–1293 . doi : 10.1080/10236190410001652720 .
• Brouwer, AE; Horvath, Gabor; Molna-Saska, Ildiko; Szabo, Csaba (2005). "En Chomp de tres filas" . Enteros . 5 : #G07.
• Friedman, Eirc J. (2007). "Dinámica no lineal en juegos combinatorios: renormalizando Chomp" . Chaos . 17 (2) 023117. Bibcode : 2007Chaos..17b3117F . doi : 10.1063/1.2725717 . PMID 17614671 . 
• Khandhawit, Tirasan; Sí, Lynnelle (2011). "Muerde gráficos y subconjuntos". arXiv : 1101.2718 [ matemáticas.CO ].
• Soltys, Michael; Wilson, Craig (2011). "Sobre la complejidad del cálculo de estrategias ganadoras para juegos de conjuntos parcialmente ordenados finitos". Theory Comput. Syst . 48 (3): 680– 692. doi : 10.1007/s00224-010-9254-y . S2CID 2720334 . 
• Brouwer, AE (2017). "El juego de morder" .
• Cho, In-Sung (2018). "Estrategias ganadoras para el juego de Chomp: Un enfoque práctico". J. History Math . 31 (3): 151– 166. doi : 10.14477/jhm.2018.31.3.151 .

• Más información sobre el juego
• Juega a Chomp online
• Todos los bocados ganadores para tamaños de hasta 14