¿Cuál es la estrategia óptima en un juego en el que los jugadores restan 7 o suman o dividen por 2?

Question

Me he inventado un juego tipo nim en el que los jugadores empiezan con un número relativamente alto y luego, en cada turno, si el número es impar, el jugador resta 7 al número o, alternativamente, si el número es par lo divide por 2 o si el número es impar añade 2. Sin embargo, el jugador no puede elegir un número negativo. El jugador que llegue a 7 gana.

Ejemplo: si el número es 11, el jugador puede restar 7 para obtener 4 o sumar 2 para obtener 13. Si el número es 16, el jugador puede restar 7 para obtener 9 o dividir por 2 para obtener 8. Ejemplo de juego:

Los jugadores comienzan con 18

Jugador 1: 18/2=9 Jugador 2: 9+2=11 Jugador 1: 11-7=4 Jugador 2: 4/2=2 Jugador 1: 2/2=1 Jugador 2: 1+2=3 Jugador 1: 3+2=5 Jugador 2: 5+2=7

El jugador 2 gana.

¿Cómo podemos predecir si en cualquier número grande el jugador con la jugada está en una posición ganadora o perdedora? ¿Es posible que para los números superiores a un determinado límite la mejor estrategia para ambos jugadores sea sumar siempre 2 para no perder?

Números ganadores y perdedores para 1-100:

1 Losing
2 Winning
3 Winning
4 Losing
5 Losing
6 Losing
7 Winning
8 Winning
9 Losing
10 Winning
11 Winning
12 Winning
13 Winning
14 Losing
15 Losing
16 Winning
17 Winning
18 Winning
19 Losing
20 Losing
21 Winning
22 Winning
23 Winning
24 Losing
25 Losing
26 Winning
27 Winning
28 Winning
29 Losing
30 Winning
31 Winning
32 Winning
33 Winning
34 Losing
35 Losing
36 Winning
37 Winning
38 Winning
39 Losing
40 Winning
41 Winning
42 Winning
43 Winning
44 Losing
45 Losing
46 Winning
47 Winning
48 Winning
49 Losing
50 Winning
51 Winning
52 Winning
53 Winning
54 Losing
55 Losing
56 Winning
57 Winning
58 Winning
59 Losing
60 Losing
61 Winning
62 Winning
63 Winning
64 Losing
65 Losing
66 Winning
67 Winning
68 Winning
69 Losing
70 Winning
71 Winning
72 Winning
73 Winning
74 Losing
75 Losing
76 Winning
77 Winning
78 Winning
79 Losing
80 Losing
81 Winning
82 Winning
83 Winning
84 Losing
85 Losing
86 Winning
87 Winning
88 Winning
89 Losing
90 Winning
91 Winning
92 Winning
93 Winning
94 Losing
95 Losing
96 Winning
97 Winning
98 Winning
99 Losing
100 Losing

Answer 1

Lema $1.1$ : Un jugador pierde si $N \in \{2,3,7,8\}$ directamente antes de que tenga que hacer un movimiento.

La prueba se deja como ejercicio para el lector.

Lema $1.2$ : Deje que el inicio $N$ sea congruente con $0$ , $1$ , $4$ , $5$ , $6$ o $9$ (mod $10$ ) y supongamos que el jugador A comienza el juego.

Entonces, si el jugador A sigue la siguiente estrategia $N$ siempre será congruente con $0$ , $1$ , $4$ , $5$ , $6$ o $9$ (mod $10$ ) antes de que se mueva y $N$ siempre será congruente con $2$ , $3$ , $7$ o $8$ (mod $10$ ) después de la mudanza. $$\begin{array}{c|c|c|} N \text{ % } 10 & \text{Move} \\ \hline 0 & -7 \\ \hline 1 & +2 \\ \hline 4 & \cdot \frac{1}{2} \\ \hline 5 & +2 \text{ if } N=5, -7 \text{ otherwise} \\ \hline 6 & \cdot \frac{1}{2} \\ \hline 9 & -7 \\ \hline \end{array}$$ Tenga en cuenta que pasar de $0$ a $-7$ no es un movimiento legal. Sin embargo, $N$ nunca será $0$ porque los únicos números no nulos que llegan a $0$ de son $-2$ y $7$ .

Prueba: Dejemos que $N_k$ sea el valor de $N$ antes de que un jugador se mueva y $N_{k+1}$ el valor de $N$ después de que ese jugador se mueva.

Consideremos la siguiente tabla de clases de congruencia (mod $10$ ) de $N_{k+1}$ para cada una de las diez posibles clases de congruencia (mod $10$ ) de $N_k$ y los dos movimientos posibles. $$\begin{array}{c|c|c|} N_k \text{ % } 10 & \text{+2} & \text{-7} & \cdot \frac{1}{2} \\ \hline 0 & - & 3 & 0, 5 \\ \hline 1 & 3 & 4 & - \\ \hline 2 & - & 5 & 1, 6 \\ \hline 3 & 5 & 6 & - \\ \hline 4 & - & 7 & 2, 7 \\ \hline 5 & 7 & 8 & - \\ \hline 6 & - & 9 & 3, 8 \\ \hline 7 & 9 & 0 & - \\ \hline 8 & - & 1 & 4, 9 \\ \hline 9 & 1 & 2 & - \\ \hline \end{array}$$ Desde $0$ , $1$ , $4$ , $5$ , $6$ y $9$ (mod $10$ ), la estrategia anterior siempre da lugar a un movimiento tal que $N_{k+1}$ es congruente con $2$ , $3$ , $7$ o $8$ (mod $10$ ).

Desde $2$ , $3$ , $7$ o $8$ (mod $10$ ), nunca existe la opción de hacer un movimiento tal que $N_{k+1}$ es congruente con $2$ , $3$ , $7$ o $8$ (mod $10$ ).

Teorema $1.3$ : Deje que el inicio $N$ sea congruente con $0$ , $1$ , $4$ , $5$ , $6$ o $9$ (mod $10$ ) y supongamos que el jugador A comienza el juego.

Entonces, si el jugador A sigue la estrategia anterior, ganará la partida.

Una pista: Por lo tanto, según el lema $1.1$ y $1.2$ sabemos que el jugador A ganará si $N$ nunca llega a $2$ , $3$ , $7$ o $8$ . La última pieza es demostrar que si el jugador A sigue la estrategia descrita en el lema $1.2$ , $N$ siempre acabará por alcanzar $2$ , $3$ , $7$ o $8$ . Obsérvese que los únicos casos en los que el jugador A realizará un aumento a $N$ es si $N$ es congruente con $1$ (mod $10$ ) o si $N$ es $5$ antes de que se mueva.

Answer 2

Llamar a un número $n$ ganar si $n$ es de la forma $10k+b$ avec $b \in \{2,3,7,8,11,16\}$ o si $n=10.4^k.(2b+1)$ ,
y llamar a $n$ perdiendo si $n$ es $1,6$ o de la forma $10k+b$ avec $b \in \{4,5,9\}$ o si $n = 20.4^k.(2b+1)$ .

Si $n$ está ganando entonces puede pasar a un número perdedor :

si $n=10k+b$ avec $b \in \{11,12,16\}$ , eliminar $7$ .
si $n=10k+b$ avec $b \in \{3,7\}$ , añadir $2$ .
si $n=2$ o $n=10k+8$ o $n=10.4^k(2b+1)$ dividir por $2$ .

Si $n$ está perdiendo, entonces sólo puede pasar a un número ganador.

Además, si siempre se pasa de un número ganador a un número perdedor (es decir, si los jugadores no se equivocan cuando se les dice que pueden ganar), el juego terminará eventualmente. Para demostrarlo basta con observar las secuencias más largas posibles de "suma $2$ " se mueve.

Si $n=10k+3$ , puedes tener $4$ "añadir $2$ " se mueve en una fila (o, si $k$ fue $0$ , se gana en dos movimientos), lo que lleva a $10k+11$ (o el jugador perdedor puede elegir ir a $10k-2$ o $10k+2$ y disminuir los números antes de que se vea obligado a hacerlo)
Añadiendo $2$ a $10k+11$ sería entregar una victoria al jugador perdedor, por lo que se ve obligado a eliminar $7$ y llegar a $10k+4$ . Y a partir de ahí, el jugador perdedor sólo puede ir a $5k+2$ o $10k-3$ (si está permitido).
Así que en general, o ganas, o llegas a uno de $10k-3,10k-2,10k+2,5k+2$ todos los cuales son más pequeños que el $10k+3$ de la que partimos.

Esto es suficiente para mostrar que los números disminuirán en general hasta que alguien gane el juego.

Answer 3

A menos que el número inicial sea $5$ o $14$ (o $7$ Supongo ) el juego nunca terminará.

He aquí la razón: Es fácil ver que $5$ y $14$ son los únicos números a partir de los cuales $7$ puede ser alcanzado. Por lo tanto, mientras cada jugador pueda evitar hacer uno de estos números, nunca perderá y el juego nunca terminará.

La única razón por la que un jugador jugaría cualquiera de los dos $5$ o $14$ Entonces, es si estos dos (o uno de estos dos) son sus únicas opciones. Pero es fácil comprobar que no hay ningún número que sólo permita jugar a cualquiera de los dos $5$ o $14$ .