Un Nim-como un juego con las condiciones y estrategias

Question

El juego:

Dado $S = \{ a_1,..., a_n \}$ de los enteros positivos ($n \ge 2$). El juego es jugado por dos personas. En cada uno de sus turnos, el jugador elige dos diferentes el número cero y resta $1$ a partir de cada uno de ellos. El ganador es el que, por última vez, ser capaz de hacer la tarea.

El problema:

Supongamos que el juego es jugado por $\text{A}$ y el de ella misma.

$\text{a)}$ Encontrar las condiciones necesarias y suficientes de $S$ (llamado $\mathbb{W}$), si hay alguno, en que $\text{A}$ siempre claro el conjunto, independientemente de cómo se juega.

$\text{b)}$ También, encontrar las condiciones necesarias y suficientes de $S$ (llamado $\mathbb{L}$) en que $\text{A}$ es siempre incapaz de despejar el conjunto, independientemente de cómo se juega.

$\text{c)}$ , Entonces, encontrar las estrategias/algoritmo mediante el cual $\text{A}$, se puede despejar el conjunto de con $S$ que no satisface $\mathbb{L} \vee \mathbb{W}$.

Siguiente, supongamos que el juego es jugado por $\text{A}$ $\text{B}$ respectivamente y $S$ que no satisface $\mathbb{W}$.

$\text{d)}$ Es que hay alguno de ellos que tienen las estrategias/algoritmo para ganar el juego? Si es así, ¿quién es ella y cuál es su ganancia? (Es posible suponer que $\text{A}$ $\text{B}$ jugar el juego de forma óptima)

$\;$

Nota:

$\text{1)}$ Esto no es una asignación. Acabo de crear esta fuera de una cosa familiar en mi vida. Así que, no sé si hay un oficial de investigación o incluso nombres para el juego. Si es así, yo estaría muy agradecido si usted compartió esos.

$\text{2)}$ El caso de $n = 2$ es tan evidente que podemos eliminar de la consideración. Podemos hacer la misma cosa una evidente condición en la $\mathbb{W}$ (si $\mathbb{W} \neq \varnothing$): $\left ( \sum_{i \in S} i \right ) \; \vdots \; 2$.

Gracias de antemano.

${}$

Actualización 1: Para borrar muchas personas a la incomprensión y a evitar a los nuevos, hago hincapié en la palabra "diferente". Y por "diferente", me refiero a diferentes índices de los números, no sus valores. Si esto todavía no está claro, creo que deberíamos considerar la $S$ como finito secuencia natural ( $a_1$ $a_n$) y no eliminar cualquiera de ellos una vez que llegan a $0$.

Actualización 2: (d) se ha renovado un poco, gracias a Greg Martin.

Answer 1

Estoy más interesado en el competitivo parte de la pregunta, así que mi respuesta se ocupa con la siguiente modificación a (d): La posición de partida puede ser cualquier secuencia de $n\ge3$ enteros positivos, independientemente de si el total de la suma es par o impar (a pesar de que, en general, la paridad no se puede cambiar durante el juego, por supuesto). El primer jugador en ser incapaz de moverse pierde, independientemente de si todos los números son $0$ todavía. Para este juego, aquí están algunos emperical observaciones.

Si $n=3$ y la paridad de la suma total es incluso: el perder posiciones son precisamente aquellos en que los tres números son individualmente, incluso. Por lo que una estrategia ganadora, una vez que hago un movimiento que los resultados en los tres números, incluso, es para restar dos números de mi oponente.

Si $n=4$ y la paridad de la suma total es incluso: el perder posiciones son precisamente aquellos donde todos los cuatro números son aún o cuatro números son impares. Una estrategia ganadora (hay otros) es siempre resta de los dos números impares.

Si $n=5$ y la paridad de la suma total es incluso: el perder posiciones son precisamente aquellos donde todos los cinco números son aún, o el número más pequeño es, incluso, y todos los demás números son impares. Estrategia ganadora: si mi oponente sale de dos números impares, restar de ellos; de otra manera restar el número más pequeño (que será raro) y el único número par.

Cuando la paridad del total es impar, ya que el juego parece más complicado. Al $n=3$, por ejemplo, perder posiciones incluyen las filas de \begin{array}{ccc} 1 & 2 & 2 \\ 1 & 4 & 4 \\ 1 & 6 & 6 \\ 1 & 8 & 8 \\ 1 & 10 & 10 \\ 2 & 2 & 5 \\ 2 & 2 & 7 \\ 2 & 2 & 9 \\ 2 & 3 & 4 \\ 2 & 4 & 7 \\ 2 & 4 & 9 \\ 2 & 5 & 6 \\ 2 & 6 & 9 \\ 2 & 7 & 8 \\ 2 & 9 & 10 \\ 3 & 3 & 3 \\ 3 & 4 & 6 \\ 3 & 5 & 5 \\ 3 & 6 & 8 \\ 3 & 7 & 7 \\ 3 & 8 & 10 \\ 3 & 9 & 9 \\ 4 & 4 & 5 \\ 4 & 4 & 9 \\ 4 & 5 & 8 \\ 4 & 6 & 7 \\ 4 & 7 & 10 \\ 4 & 8 & 9 \\ 5 & 5 & 7 \\ 5 & 6 & 6 \\ 5 & 6 & 10 \\ 5 & 7 & 9 \\ 5 & 8 & 8 \\ 5 & 10 & 10 \\ 6 & 6 & 9 \\ 6 & 7 & 8 \\ 6 & 9 & 10 \\ 7 & 7 & 7 \\ 7 & 8 & 10 \\ 7 & 9 & 9 \\ 8 & 8 & 9 \\ 9 & 10 & 10 \end{array} mientras la ganancia de posiciones incluyen las filas de \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 3 \\ 1 & 1 & 5 \\ 1 & 1 & 7 \\ 1 & 1 & 9 \\ 1 & 2 & 4 \\ 1 & 2 & 6 \\ 1 & 2 & 8 \\ 1 & 2 & 10 \\ 1 & 3 & 3 \\ 1 & 3 & 5 \\ 1 & 3 & 7 \\ 1 & 3 & 9 \\ 1 & 4 & 6 \\ 1 & 4 & 8 \\ 1 & 4 & 10 \\ 1 & 5 & 5 \\ 1 & 5 & 7 \\ 1 & 5 & 9 \\ 1 & 6 & 8 \\ 1 & 6 & 10 \\ 1 & 7 & 7 \\ 1 & 7 & 9 \\ 1 & 8 & 10 \\ 1 & 9 & 9 \\ 2 & 2 & 3 \\ 2 & 3 & 6 \\ 2 & 3 & 8 \\ 2 & 3 & 10 \\ 2 & 4 & 5 \\ 2 & 5 & 8 \\ 2 & 5 & 10 \\ 2 & 6 & 7 \\ 2 & 7 & 10 \\ 2 & 8 & 9 \\ 3 & 3 & 5 \\ 3 & 3 & 7 \\ 3 & 3 & 9 \\ 3 & 4 & 4 \\ 3 & 4 & 8 \\ 3 & 4 & 10 \\ 3 & 5 & 7 \\ 3 & 5 & 9 \\ 3 & 6 & 6 \\ 3 & 6 & 10 \\ 3 & 7 & 9 \\ 3 & 8 & 8 \\ 3 & 10 & 10 \\ 4 & 4 & 7 \\ 4 & 5 & 6 \\ 4 & 5 & 10 \\ 4 & 6 & 9 \\ 4 & 7 & 8 \\ 4 & 9 & 10 \\ 5 & 5 & 5 \\ 5 & 5 & 9 \\ 5 & 6 & 8 \\ 5 & 7 & 7 \\ 5 & 8 & 10 \\ 5 & 9 & 9 \\ 6 & 6 & 7 \\ 6 & 7 & 10 \\ 6 & 8 & 9 \\ 7 & 7 & 9 \\ 7 & 8 & 8 \\ 7 & 10 & 10 \\ 8 & 9 & 10 \\ 9 & 9 & 9. \end{array}

Answer 2

Esta respuestas de las partes a)-c).

El conjunto $\mathbb{W}$ es bastante pequeña: Se compone de conjuntos de $S=\{a,a\}$ $S=\{1,\ldots,1\}$ con un número de $1$'s. Todos los demás pueden, por (en)juiciosa jugar, llevar a una posición perdedora de la forma $S=\{a\}$. Esto puede ser demostrado por inducción sobre el total de los números enteros en $S$: Si $S$ no es uno de los dos tipos especificados (y aún no un solo número), puede ser menor, pero todavía no de cualquier tipo en $\mathbb{W}$, restando $1$ de cada uno de los dos más pequeños números, a menos que $S=\{1,1,a,a\}$$a\gt1$, en cuyo caso restando $1$ de $1$ $a$ , lo que deja a $\{1,a-1,a\}$, hace el truco.

El conjunto $\mathbb{L}$ se compone de conjuntos de $S$ para que el total de los números enteros es un número impar, y establece para que el mayor número entero es mayor que la suma de los otros. Esto es demostrado una vez más por inducción, que se basa en el hecho de que hagas lo que hagas, el conjunto más pequeño después de un juego se ha hecho todavía tienen un extraño suma o su mayor número aún superior a la suma de los otros números.

Como un solitario estrategia para la limpieza de la set (cuando sea posible), simplemente cantidades para siempre restando $1$ desde el elemento más grande; el otro $1$ puede ser restado de nada.

Answer 3

Un hilo viejo, pero me di cuenta de que en el "relacionados con la"s para otra pregunta, y lo encontré interesante.

Permítanme presentarles el juego de "gotas de lluvia": tiene un vertical de la pista de algún número finito de "niveles" y en cada nivel es un número finito de gotas de lluvia. Durante cada turno del jugador, se trasladan de una gota de lluvia en dos niveles o dos gotas de lluvia abajo 1 nivel de cada uno, con la restricción de que los dos gotas de lluvia no puede empezar en el mismo nivel. Las gotas de lluvia en la parte inferior de la pista de moverse de la junta (que cuenta como 1 nivel, no dos). El juego continúa hasta que un jugador no puede hacer que su o sus dos movimientos, en cuyo caso el otro jugador gana.

¿Por qué introducir este otro juego? Porque es el mismo juego, en el disfraz. Después de cada movimiento en el juego de este hilo, reorganizar las pilas en una fila vertical, en orden ascendente, como usted se mueve hacia abajo. I. e., la más pequeña de las pilas en la parte superior, y el más grande en la parte inferior. Esto es irrelevante para el juego de este juego, ya que no depende de alguna manera de la disposición de las pilas. Ahora traducirlo a mi juego restando de cada pila de la cantidad de piedras en la pila inmediatamente anterior. La parte superior de la pila es igual. En virtud de esta metamorfosis, un cambio en su juego se convierte en un movimiento en la mía, y viceversa si se invierte el proceso.

Entonces, ¿qué podemos deducir de las gotas de lluvia? Llame al nivel inferior de la "piscina". Claramente, el juego termina cuando todos los niveles de la piscina han sido vaciados. Además, si el número de niveles, comenzando con el grupo = nivel de $0$, y aumenta a medida que ascendemos, y si $r_i$ es el número de gotas de lluvia en el nivel de $i$ en el inicio del juego, y $D$ es el número de gotas de lluvia "drenado de la piscina" (es decir, alejado de la junta) durante el juego, entonces el número total de movimientos es $\left(\sum nr_n\right) + D$, y el número total de vueltas es la mitad de eso. Si el número de vueltas es impar, entonces el Jugador 1 ganado. Si es par, entonces el Jugador 2 ganó. De ello se sigue que el juego está totalmente determinado por la posición inicial y cuántas gotas de lluvia se eliminan completamente de la junta.

Yo creo que la cuestión de que las posiciones se gana puede ser determinado a partir de esto, pero estoy fuera de tiempo ahora para proseguir.