¿Estrategia ganadora para el segundo jugador?

Question

Supongamos que nuestro juego de dos jugadores consiste en que construyen una secuencia binaria (0 y 1) eligiendo por turnos alternativos escribir cero o uno en cada turno, y ampliando así la secuencia en uno en cada turno.

Antes de empezar el juego, se nos da un número $n$ . El juego continúa hasta que algún bloque de $n$ dígitos consecutivos se encuentra por segunda vez (las dos apariciones del bloque pueden solaparse). El jugador que complete este segundo bloque o bloque duplicado pierde.

Claramente este juego es finito como un límite simplista de $2^n+n-1$ sobre el número de dígitos de la secuencia basta como prueba por pigenholeing

Si $n$ es impar, ¿cómo se demuestra que el segundo jugador (el que escribe el segundo número de la secuencia) tiene una estrategia ganadora independientemente de lo que haga el primero? ¿Es aplicable aquí algún tipo de argumento de robo de estrategia?

Answer 1

Sea $n$ sea impar y sea $s_t \in \{0,1\}$ sea el $t^{th}$ dígito binaray seleccionado. El índice del número impar $t$ denota jugador $1$ e incluso el índice $t$ es jugador $2$ turno. Si el jugador $2$ utiliza la estrategia:

$$s_{q} = 1-s_{q-1} \qquad (\star)$$

por cada par $q$ entonces jugador $2$ ganará. Para demostrarlo, veamos $j$ sea el menor número en el que $s_{i}s_{i+1}\dots s_{i+n-1}$ es la primera aparición de un bloque de $n$ dígitos con la segunda aparición correspondiente $s_{j}s_{j+1}\dots s_{j+n-1}$ .

En primer lugar, observe que si $j$ es impar entonces jugador $1$ pierde. Por lo tanto, mostraremos si $j$ es incluso tendremos una contradicción.

Si $j$ es par y $i$ es par, entonces la secuencia $s_{i-1}s_{i}\dots s_{i+n-2}$ y $s_{j-1}s_{j}\dots s_{j+n-2}$ son iguales porque $s_{j} = s_{i}$ y estrategia ( $\star$ ) implica que $s_{j-1}=s_{i-1}$ . Esto contradice el hecho de que $j$ es el número más pequeño en el que se encuentra un bloque por segunda vez.

Si $j$ es par y $i$ es impar entonces, \begin{align} s_{j} &= 1-s_{j-1} &&= s_{i} \\ s_{j+1} &= &&= s_{i+1} = 1-s_{i} \\ s_{j+2} &= 1-s_{j+1} &&= s_{i+2} \\ s_{j+3} &= &&= s_{i+3} = 1-s_{i+2} \\ s_{j+4} &= 1-s_{j+3} &&= s_{i+4} \\ \vdots \end{align} Observe que $s_{j+4} = 1-s_{j+3} = 1-s_{i+3} = 1-(1-s_{i+2}) = s_{i+2} = s_{j+2}$ y de forma similar, $s_{i+5} = 1-s_{i+4} = 1-s_{j+4} = 1-(1-s_{j+3}) = s_{j+3} = s_{i+3}$ . Siguiendo este patrón se puede demostrar que $s_{j}=s_{j+2}=s_{j+4}= \dots = s_{j+n}$ y $s_{i+1}=s_{i+3}=s_{i+5}= \dots = s_{i+n-1}$ . Desde $s_{i+1}=1-s_{i} = 1-s_{j}$ esto implica que $s_{j}s_{j+1}\dots s_{j+n-1}$ es alterna $0$ y $1$ es decir, $010101\dots$ ou $101010\dots$ .

Sin pérdida de generalidad, supongamos que $s_{i} = 1$ . Desde $n$ es impar sabemos $s_{i+n-1}=1$ y por $(\star)$ sabemos que $s_{i+n} = 0$ . Además, sabemos que $s_{j} = 1$ y por $(\star)$ sabemos que $s_{j-1}=0$ . Sin embargo, tenga en cuenta que $s_{i+1}s_{i+2}\dots s_{i+n}$ es lo mismo que $s_{j-1}s_{j}\dots s_{j+n-2}$ . Si $j-1 \neq i+1$ entonces esto contradice el hecho de que $j$ es el número más pequeño en el que se encuentra un bloque por segunda vez. Si $i+1=j-1$ entonces $s_{i}\dots s_{i+n-1}$ es lo mismo que $s_{i+2}\dots s_{i+n+1}$ y jugador $1$ pierde.

Por lo tanto, $s_{q} = 1-s_{q-1}$ para todos incluso $q$ es la estrategia ganadora cuando $n$ es impar.