$A$ y$B$ se turnan para elegir enteros:$A$ elige un número entero y luego$B$ picks$k > 1$ enteros ($k$ se está arreglando). Un jugador no puede elegir un número que su oponente ha elegido. Si$A$ tiene enteros$5$ que forman una secuencia aritmética, entonces gana$A$. El objetivo de$B$ es evitar que eso suceda. ¿Quién tiene una estrategia ganadora (después de un número finito de turnos)? ¿Depende de$k$?
Respuestas
¿Demasiados anuncios?
Yo reclamo que Un Jugador tiene una estrategia ganadora en el juego, y además, es una estrategia ganadora para ella, simplemente, jugar el menor número disponible.
Permítanme considerar el juego junto con varias variaciones naturales.
El jugador a gana el original de una progresión aritmética de juego. Para ser un poco más específico sobre el juego, consideremos lo que me gustaría proponer que llamamos la progresión aritmética juego de $G_k^n$ para enteros positivos $k$ e $n$, un juego de dos jugadores de la información perfecta. En cada turno, Un jugador juega una nueva entero y el jugador B juega a $k$ números enteros, con todos los números sorteados distintas; Un jugador gana si hay una progresión aritmética de longitud $n$ entre sus números, y el jugador B tiene el objetivo de prevenir esto.
En esta notación, el original juego de es $G_k^5$. Estos son todos los juegos abiertos para Un jugador, lo que significa que cualquier victoria para el jugador a, si ocurre, se producen en un determinado escenario de juego. Se sigue por la Gale-Stewart teorema de que uno de los jugadores tiene una estrategia ganadora.
Pero en realidad, podemos describir explícitamente una estrategia ganadora para el jugador a: que, simplemente, jugar los más pequeños disponibles entero positivo. Me parece interesante que la misma estrategia funciona de manera uniforme en $n$ e $k$, y Un jugador no tiene que conocer estos parámetros de juego por adelantado. Además, la estrategia no dependen de la historia del juego, pero sólo en la actual conjuntos de ya-interpretado números.
Para ver que esto es una estrategia ganadora, considere la posibilidad de cualquier infinita de jugar al juego juega de acuerdo a ella. Para tal obra, la observación clave es que esta estrategia asegura que el conjunto de los números jugados por Una tendrá proporción de al menos $1/(k+1)$ en cualquier segmento inicial de los enteros positivos. En particular, el conjunto jugado por Una voluntad positiva asintótica de la densidad. Se sigue por el teorema de Szemerédi que el conjunto jugado por Una debe contener progresiones aritméticas arbitrariamente largas. Así que Un jugador le han ganado ya en algún momento. Por lo que es una estrategia ganadora.
Vamos a considerar varias variaciones naturales del juego.
El jugador a gana el arbitrariamente larga finita progresiones de juego. Considere la posibilidad de un infinito versión del juego, que se denota $G_k^{<\omega}$, en donde el juego continúa a través de todas las finito de etapas, y el jugador a gana un infinito juego si el conjunto de sus números contiene progresiones aritméticas de cada longitud finita. El argumento anterior, usando el teorema de Szemerédi muestra que el play-la-menor-disponible-número de la estrategia es todavía una estrategia ganadora para el jugador en este juego modificado, ya que puede asegurarse de que su conjunto tiene de densidad positiva y por lo tanto contiene progresiones aritméticas de cualquier longitud deseada.
El jugador B gana la infinita progresión aritmética de juego. Si queremos modificar el ganador de la condición del juego, sin embargo, para el juego de $G_k^\omega$, donde el jugador a gana sólo cuando su set contiene una infinita progresión aritmética, entonces me afirmación de que el jugador B tiene una estrategia ganadora. La razón es que no son sólo countably muchos infinito progresiones aritméticas de los números enteros, ya que cada uno está determinado por su punto de partida y la diferencia. Ya que hay sólo un número finito de números jugados por cualquier finito dado etapa de juego, se deduce que el jugador B puede bloquear el $n^{th}$ infinita progresión aritmética con un número único jugado en la jugada $n$. Así que incluso cuando $k=1$, el jugador B tiene una estrategia ganadora para bloquear una infinita progresión aritmética de Un conjunto.
El jugador B gana la variante, donde el $k$ no es fijo. Por último, considere la versión del juego donde $k$ no es fijo, por lo que el jugador B es libre para jugar cualquier conjunto finito en cada movimiento. Podemos denotar por $G_{<\omega}^n$. Para esta variante, el jugador B tiene una estrategia ganadora para bloquear todas las progresiones aritméticas incluso de longitud $n=3$ para A. La estrategia es simplemente para llenar en todos los números hasta el doble de la actual mayor número de jugadas. De esta manera, no hay tres números jugado por Una puede tener sus diferencias en una progresión aritmética, ya que cada número siguiente desempeñado por Una mayor diferencia de cualquiera de los dos números anteriores. Así que esta es una estrategia ganadora para evitar Un formen una progresión aritmética de longitud $3$.
Más comentarios y preguntas. En el original de la $G_k^n$ juego, el juego-la-menor-disponible-número de la estrategia es una estrategia ganadora, pero no estoy seguro de cuánto tiempo toma para ganar, o si esta estrategia es eficiente en el sentido en ganar. Tal vez la combinatoria finita expertos puede colocar límites en cuánto tiempo el juego se llevará. Presumiblemente, existe un número $N$, dependiendo de la $n$ e $k$, de tal manera que Un jugador puede forzar la victoria en la mayoría de los $N$ se mueve, pero no sé cómo de grande $N$ o incluso si hay un $N$. La existencia de un número $N$ es equivalente a la afirmación de que este juego tiene un número finito de valor de la partida (pero tenga en cuenta que no todos los juegos abiertos tienen un número finito de valor de la partida).
Pregunta 1. Cómo rápidamente puede Un jugador gana el juego el $G_k^n$? ¿El play-la-menor-disponible-número de la estrategia de lograr el mejor bound?
Pregunta 2. Fijo $n$ e $k$, hay un uniforme enlazado $N_k^n$ para la longitud de jugar, no dependiendo de los movimientos del jugador B?
En el juego donde los $k$ no es fijo, uno se puede imaginar que el juego de $G_f^n$, en función de las $f:\mathbb{N}\to\mathbb{N}$ se utiliza para especificar el tamaño de la $f(i)$ del conjunto interpretada por B en la jugada $i$. El argumento que dio muestra de que si $f$ es lo suficientemente exponencial, entonces el jugador B gana. Entre tanto, la constante de las funciones de $f(i)=k$ corresponden a la original de una progresión aritmética de juego.
Pregunta 3. Para que las funciones de $f$ hace Un jugador todavía tiene una estrategia ganadora? Por ejemplo, si $f$ es lineal o incluso polinomio, hace Un jugador tiene una estrategia ganadora? Lo que si $f=o(2^i)$?
Matthew
Puntos
111
Joel respuesta utiliza maquinaria pesada para dar un mayor resultado. A continuación es un buen resultado para $k=1$ el uso de pesados cálculos (no la mía.)
Mi sospecha es que la pregunta, tal como solicitó puede ser relativamente simple estrategia. Sin embargo no tengo uno.
Para $k=1,$ a Un jugador puede ganar, incluso con la restricción adicional de que la progresión $1 \leq a,a+d,a+2d,a+3d,a+4d$ debe tener $d \in \{1,14,15,16\}$ e $a+4d \leq 225$ y $B$ gana si se obtiene como una progresión aritmética.
Esto se basa en el juego de go-moku juega en un $15 \times 15$ junta. De acuerdo con el artículo vinculado, equipo de análisis de muestra de que el juego es un primer triunfo de jugador. La numeración de la cuadrícula se cruzan $(i,j)$ con $i+15(j-1)$ da la correspondencia. Desde que los seres humanos todavía jugar el juego en los torneos, no es trivial para encontrar una estrategia (aunque puede haber reglas, incluso las cosas).
Permitiendo arbitraria progresión aritmética da muchas más maneras de ganar, a pesar de $k \gt 1$ también es una ventaja para B.
Matthew
Puntos
111
La estrategia minimalista para $A$ de "no pienses, sólo elegir el más pequeño unchosen entero no negativo!" tiene una simple estrategia para $B$ que es interesante analizar qué tan lejos llega antes de que finalmente falla. Me pregunto cómo de buena es.
El número de vueltas para $A$ antes de ganar aumenta exponencialmente con la $k$ (siempre $A$ utiliza esta estrategia minimalista y $B$ utiliza el que voy a describir.) Esto es cierto también para ti término progresiones aritméticas.
Considerar el juego donde $A$ necesidades para conseguir una progresión aritmética de longitud $m$ a ganar y $B$ pasa $k$ opciones de cada turno. Entonces creo que mi estrategia para $B$ emparejado con la estrategia minimalista para $A$ tienen $A$ ganar en un turno no menor de $k^c$ donde $$c=\log_{\frac{m}{m-1}}(m-1).$$
Una mejor estrategia (para el plazo de tres secuencias) por $A$ ganaría en $k+2$ giros (esto podría fácilmente ser mejorado a $\frac{k}3$ turnos.) Aproximadamente, en el primer $k$ vueltas $A$ selecciona disponibles, incluso los números de $a_1,\cdots,a_{k}$, entonces, sea cual sea la decisión $B$ ha hecho hasta el momento, es posible elegir una, incluso,$a_{k+1}$, de modo que ninguno de $\frac{a_{k+1}-a_i}2$ han elegido todavía. $B$ debe salir de uno de esos unchosen en su turno por lo $A$ recoge que la próxima vez y gana.
Cómo extender a más progresiones no está claro, sin embargo, que el argumento muestra que wlog $A$ consigue tres libre se mueve en la primera vuelta (se podría organizar de que toda la progresión determinada por $a_i,a_{k+1}$ es gratuito).
A continuación es una estrategia para $B$ si ella está segura de que $A$ le siguen ciegamente la estrategia minimalista. Los movimientos son conocidos de antemano por lo que es sólo una cuestión de cuándo $A$ gana. Para facilitar el análisis me permitirá $k \gt 0$ a ser cualquier número real y lo interpretan como: en la vuelta $t$ si $B$ ya ha elegido a $m$ enteros ella ha $\lfloor kt \rfloor-m$ disponible de movimientos y puede hacer ninguno o todos o algunos y guardo el resto para futuras vueltas.
La estrategia es que ella va a la recogida en la orden de los enteros no negativos con un $4$ en su base de $5$ expansión y deje $A$ trabajo a través del resto de una en una. Esto bloquea cualquier $5$ plazo progresiones mientras $B$ se mantiene por delante. Sin embargo $B$ va a salvar a sus movimientos y elegir sólo lo suficiente números que $A$ no va a ganar en la vuelta siguiente (que puede llegar a tomar más movimientos que ella tiene).
Al $B$ pierde es porque $A$ fue capaz de jugar un número en algún intervalo $[5^j-5^{j-1},5^j-1].$ Esto sucederá en el caso de que $$\frac{5^{j-1}-4^{j-1}}{4^{j-1}} \leq k \lt \frac{5^{j}-4^{j}}{4^{j}}.$$ The exact winning move depends on where $k$ cae en ese rango.
Por ejemplo, Si $k \geq \frac{61}{64} =0.953125$ entonces $A$ en algún momento de la coge $125$ sin haber ganado. No se producen problemas hasta después de la vuelta al $A$ picks $468=3333_5.$ En este punto cualquier cosa en $[469,624]$ sería un ganador para $A$ en el siguiente movimiento. Pero $B$ ha mueve en reserva, sin duda lo suficiente para elegir a todos los de $[629,499].$ sin Embargo, para ser capaces de seguir adelante y elegir todos los de $[500,634]$ requiere $k \geq \frac{369}{256}=1.44140625.$ Si es así, entonces todo está bien, al menos hasta el $2499.$
