¿Infinite Chomp es un juego finito?

Question

Considere la $(\omega \times \omega)$ versión de Chomp . Se dice que aquí que la versión de chomp on an infinite chocolate bar es de hecho un juego finito. Esta afirmación me confunde. ¿No es posible que los dos jugadores por turno tomen una $(1 \times 1)$ ¿morder el chocolate, por ejemplo, sólo en la fila superior? ¿Se trata, por tanto, de un juego infinito? ¿O es un morder $(n \times m) \in \mathbb{N}^2$ resultando en una barra de chocolate finita después del primer movimiento. Sólo tengo esta definición informal del problema que me resulta confusa.

Answer 1

Creo que la distinción que puede estar perdiendo aquí es la diferencia entre $\omega$ como set - es decir, el conjunto de todos los números naturales $\{0,1,2,\ldots\}$ - y $\omega$ como ordinal la entidad que corresponde a la ordenación $0\lt1\lt2\lt3\lt\ldots$ de los naturales. Es evidente que ambos conceptos están estrechamente relacionados, pero no son del todo idénticos; por ejemplo, consideremos $\omega+\omega$ definido como el conjunto $\{0,1,\ldots,\omega, \omega+1, \ldots\}$ y de forma similar como la ordenación $0\lt1\lt\ldots\lt\omega\lt\omega+1\lt\ldots$ en esas entidades. Entonces hay un simple isomorfismo desde el set $\omega+\omega$ al conjunto $\omega$ para todos los enteros $i$ Mapa $i$ a $2i$ y el mapa $\omega+i$ a $2i+1$ . Pero los dos no son isomorfos como pedido conjuntos; cada elemento de $\omega$ tiene un predecesor inmediato, pero el elemento $\omega$ en el orden $\omega+\omega$ no tiene ninguno. Para ver por qué los ordinales son el concepto correcto, considere el casi trivial $1\times\omega$ versión de Chomp; entonces las posiciones de este juego corresponden precisamente a los ordinales $0, 1, \ldots, \omega$ y podemos pasar de una posición $P$ a una posición $Q$ precisamente si $Q\lt P$ ; tenemos un orden natural en las posiciones.

Ahora, echemos un vistazo a la $2\times\omega$ caso: posiciones de $2\times\omega$ Chomp no son ordinales en sí mismos (son pares $(m,n)$ con $0\leq m\leq n\leq\omega$ ), pero el punto clave es que podemos ponerlos en correspondencia uno a uno con los ordinales, de tal manera que cada movimiento legal de chomp nos lleva a un ordinal inferior es decir, hay una que preserva el orden isomorfismo entre ambos. Para ver esto, podemos dividir las cosas en dos casos: $n$ finito y $n=\omega$ . Para $n$ finito, obviamente hay $n+1$ valores diferentes $(0,1,\ldots,n)$ para $m$ cada uno de ellos es alcanzable desde las posiciones con el mismo $n$ y superior $m$ pero ninguno es alcanzable desde cualquier posición con menor $n$ para que podamos pedirlos $(0,0)\lt(0,1)\lt(1,1)\lt(0,2)\lt(1,2)\lt\ldots$ - es decir, aumentando $n$ con $m$ aumentando dentro de cada valor de $n$ debería ser capaz de construir un pedir isomorfismo que mapea esta porción del orden global de posiciones en el orden $\omega$ . Ahora, 'después' de estos podemos poner todas las posiciones con $n=\omega$ y $m$ finito, ordenado por $m$ : $(0,\omega)\lt(1,\omega)\lt(2,\omega)\ldots$ esto es trivialmente isomorfo de orden a $\omega$ . Y finalmente, después de todo esto viene la posición inicial $(\omega,\omega)$ . Esto nos da una en general orden del tipo de orden $\omega+\omega+1$ en el conjunto de todos los $2\times\omega$ Posiciones de Chomp; sabemos que desde cualquier posición dada $P$ cualquier movimiento legal a una posición $Q_i$ tendrá $Q_i\lt P$ bajo esta ordenación.

¿Cómo ayuda esto? Bueno, ayuda porque los ordinales son (esencialmente por definición) bien ordenado - cualquier conjunto de ordinales tiene un elemento menor, por lo que en particular no puede haber un infinito descendente cadena $O_0\gt O_1\gt O_2\gt\ldots$ (esto está estrechamente relacionado con el axioma de fundamento/axioma de regularidad en la teoría de conjuntos). Como han dicho otros, esto es lo que significa que el juego sea finito; no hay un límite específico sobre la duración del juego, pero no hay infinito secuencia de jugadas disponibles desde la posición inicial.

El $\omega\times\omega$ El caso es sustancialmente más complicado, pero sigue siendo objeto de un análisis similar; la clave es que cada posición puede ser asignada a algún ordinal de forma que se mantenga el orden. Una forma de hacerlo: supongamos que el bocado inicial está en $(m,n)$ con $n\gt m$ (se aplica una simetría obvia). Entonces podemos pensar que la mordida divide la barra en dos $n\times\omega$ Las barras de chomp, las sobras "horizontales" y "verticales $B_h$ y $B_v$ (con una de estas sub-barras ya masticada a un $m\times\omega$ pieza). Pero como cada $B_h$ y $B_v$ es una subposición de a $n\times\omega$ posición, hay ordenamientos individuales horizontales y verticales $H = (H_0\lt H_1\lt\ldots)$ y $V = (V_0\lt V_1\lt\ldots)$ en ellos (puede ver cómo pedir el $n\times\omega$ posiciones para cualquier $n$ de forma análoga a la $2\times\omega$ posiciones); y podemos combinar las ordenaciones horizontales y verticales para formar el producto orden, $H\cdot V = ((H_0, V_0)\lt (H_1,V_0)\lt\ldots\lt(H_0,V_1)\lt(H_1,V_1)\lt\ldots)$ (ver http://en.wikipedia.org/wiki/Ordinal_arithmetic para más detalles sobre este proceso). Por último, podemos apilar todas estas posiciones aumentando $n$ (el "tamaño" del bocado original - o más abstractamente, el valor más pequeño de $n$ tal que no haya puntos sin comer al noreste de $(n,n)$ ). Es difícil juntar todo esto, pero espero que puedas tener una idea de cómo esto ofrece un buen ordenamiento general en el conjunto de posibles $\omega\times\omega$ Posiciones de chomp. Una vez que tenemos ese ordenamiento, el tipo específico no es relevante - simplemente el hecho de que es un buen ordenamiento es suficiente para que se aplique el principio de bien fundado y para que concluyamos que el juego es finito.

Answer 2

Dice que un juego "finito" es aquel que tiene garantizado su final. Este es el caso de Chomp.

Consideremos un par de ejemplos más sencillos que ilustran el mismo punto. En el juego A, el jugador 1 comienza nombrando un número entero positivo cualquiera. El jugador 2 nombra entonces un entero positivo estrictamente menor. Los jugadores se alternan nombrando números enteros cada vez más pequeños; el jugador que nombra el 1 deja a su oponente sin movimiento legal, y así gana.

Está claro que el Juego A es finito; no puede continuar para siempre. De hecho, después de la primera jugada del jugador 1, se puede poner un límite superior al número de movimientos que tardará en terminar. Pero antes de ese primer movimiento, usted no puede limita el tiempo que se tarda en terminar el juego.

En la partida B, el tablero es un cuarto de tablero infinito que se extiende eternamente hacia el norte y el este. El jugador 1 comienza colocando una ficha en cualquier casilla del tablero. Un movimiento legal es entonces mover la ficha cualquier número de casillas hacia el borde oeste, o para mover la ficha a cualquier cuadrado de una fila que está más al sur. Observe que una vez que la ficha está en la primera fila (más al sur), el juego es esencialmente el Juego A. Así que una vez que la ficha está en la primera fila, el juego puede ser acotado: si la ficha está en la $n$ de la primera fila, el juego dura como máximo $n$ más movimientos.

Pero supongamos que la ficha está en el $n$ cuadrado de la segundo fila. El juego no puede tener límites, pero tampoco puede durar eternamente. Porque después de un máximo de n se mueve, la ficha debe estar en la primera fila, y en ese momento puede estar acotado.

Ahora supongamos que la ficha está en el $n$ de la tercera fila. El juego no puede tener límites, pero tampoco puede durar eternamente. Porque después de un máximo de n se mueve, la ficha debe estar en la segunda (o primera) fila y aunque no sea acotada entonces, podemos al menos poner un límite a cuánto tiempo antes de que es limitado.

Después del primer movimiento del jugador 1, la ficha está en algunos y, aunque no podemos determinar cuánto durará el juego, podemos estar seguros de que no puede durar eternamente, porque después de un número limitado de movimientos, la ficha debe desplazarse hacia el sur. Antes del primer movimiento del jugador 1 no podemos hacer eso, pero podemos todavía estar seguros de que el juego no será eterno, porque podemos garantizar que después de un número acotado de movimientos (1 movimiento, de hecho) podremos acotar el número de movimientos antes de que podamos acotar el número de movimientos antes de (etc.) podamos acotar el juego. El juego es ilimitado, pero debe terminar en algún momento.

Chomp en una barra de chocolate infinita es de este tipo. El primer mordisco deja un número finito de filas y columnas infinitas, y aunque no podemos acotar el juego en ese punto, sí podemos acotar el número de movimientos antes de que el número de filas y columnas infinitas deba reducirse. Por lo tanto, aunque el juego no tenga límites, debe terminar en algún momento.

Answer 3

El juego no es finito en el sentido de que hay un número $N$ y podemos probar que el juego terminará en $N$ se mueve. Es finito en el sentido de que el juego no puede ser eterno. Considere la $2\times \infty$ ejemplo. El primer movimiento debe tomar un bocado de la fila superior. Ahora queda un número finito de piezas en la fila superior. Eventualmente, un jugador también tomará un bocado de la fila inferior (porque sólo había un número finito de movimientos disponibles en la fila superior después del primer movimiento, esto tiene que suceder). Una vez que un jugador toma un bocado de la fila inferior, hay un número finito de piezas restantes.

Answer 4

Desde Wikipedia :

Los jugadores eligen por turnos un bloque y se lo "comen" (lo retiran del tablero), junto con los que están debajo de él y a su derecha. El bloque superior izquierdo está "envenenado" y el jugador que se lo coma pierde.

Así que tu estrategia sugerida, que los dos jugadores por turno tomen una $(1\times 1)$ mordiendo el chocolate sólo en la fila superior, no funcionará porque una vez $(1,n)$ (el cuadrado de la fila $1$ y la columna $n$ ) es eliminado, $(1,m)$ se elimina para todos los $m>n$ .

La cuestión es que una vez $(a,b)$ se come, se considera la esquina superior izquierda de una barra de chocolate que se convierte en completamente comido. Así, cada movimiento elimina (potencialmente) una gran parte de la barra de chocolate. Deberías ser capaz de convencerte de que, debido a esto, el juego no puede ser eterno. PRUEBA .