Tableros Hackenbush con columnas tricolores: ¿es necesario añadir el tablero "arco iris" para estabilizar?

Question

Esta es una pregunta sobre "Hackenbush tricolor sólo para columnas". Formalmente, un tablero es una suma formal finita (o multiconjunto, si se prefiere) de cadenas finitas de $\{1,2,3\}$ . Para $i\in\{1,2,3\}$ y un tablero $B$ , a traslado legal $B$ para el jugador $i$ consiste en sustituir una ocurrencia de una cadena $\sigma\in B$ con una aparición de una cadena $\tau$ tal que $\tau i\preccurlyeq\sigma$ . (Intuitivamente, una cadena $\sigma$ que se producen en $B$ representa una "pila de aristas" etiquetadas según $\sigma$ desde cero). Como en una pregunta mía anterior sobre el modus operandi definen el "tipo básico" de un tablero $B$ el conjunto $bt(B)$ de pares $(x,A)$ tal que $x\in \{1,2,3\}$ , $A$ es un subconjunto propio no vacío de $\{1,2,3\}$ y existen estrategias $\pi_a$ para $a\in A$ que cuando se siguen garantizan que el primer jugador que no pueda moverse no estará en $A$ asumiendo jugador $x$ comienza y el movimiento ordenado procede en el orden cíclico obvio a partir de entonces. (Intuitivamente, $(x,A)\in bt(B)$ significa "equipo $A$ puede evitar perder en $B$ si $x$ va primero").

Ahora dejemos que ${\bf z}=\langle 1\rangle+\langle 2\rangle+\langle 3\rangle$ ser el tablero "arco iris". Curiosamente, y en contraste con la versión bicolor, añadir ${\bf z}$ hace n preservar el tipo básico. Por ejemplo, tenemos $(1,\{3\})\in bt(\langle 123\rangle)$ pero $(1,\{3\})\not\in bt(\langle 123\rangle+{\bf z}$ ). Esencialmente, añadir una copia de ${\bf z}$ permite a los jugadores $1$ y $2$ intercambian papeles durante una ronda, y eso les ayuda a vencer $3$ si $1$ va primero.

A pesar de ello, tengo curiosidad por saber si añadir ${\bf z}$ hace finalmente preservar el tipo básico:

Para una junta $B$ ¿existe necesariamente un número natural $k$ tal que $$bt(B+m{\bf z})=bt(B+n{\bf z})$$ siempre que $m,n\ge k$ ?

Aquí $aC=C+C+C+...+C$ ( $a$ veces) para $a\in\mathbb{N}$ y $C$ una tabla. También me interesaría conocer la respuesta a la pregunta análoga para $p>3$ jugadores.

Answer 1

Sí, el tipo básico de $B+n{\bf z}$ siempre se estabiliza.

Para los equipos $A$ de tamaño $2$ añadiendo una copia de ${\bf z}$ siempre es débilmente beneficioso para $A$ . En concreto, para todos los $x\in\{1,2,3\}$ si $(x,A)\in bt(B)$ entonces $(x,A)\in bt(B+{\bf z})$ . Esto se debe a que el equipo $A$ puede ignorar el ${\bf z}$ componente, utilizando su estrategia ganadora para $B$ parte, y responder al tercer jugador que juega en ${\bf z}$ jugando en ${\bf z}$ durante los dos próximos turnos.

Por la misma razón, para equipos de tamaño $1$ añadir una copia de nunca es útil, ya que el oponente es un equipo de tamaño $2$ .

En cualquier caso, hemos demostrado que la condición de miembro de $(x,A)$ en $bt(B+n{\bf z})$ como $n\rightarrow\infty$ deben converger.

---

De hecho, esto es cierto para cualquier número de jugadores:

Sea $p$ el número de jugadores, y $x\in\{1,\dots,p\}$ y que $A$ sea un equipo propio no vacío. Dividir el juego en rondas donde cada ronda es una secuencia de $p$ movimientos consecutivos empezando por el jugador inicial, $x$ . Para un partido jugado en $B+n{\bf z}$ , llamar a una ronda aburrido si todos $p$ movimientos de esa ronda se juegan en una de las ${\bf z}$ componentes. En el juego óptimo, se puede suponer que todas las rondas aburridas ocurren al final de la partida. De hecho, supongamos que existe una línea de juego óptima en la que el número de rondas $i$ es aburrido, pero el número redondo $i+1$ es interesante. Supongamos que el equipo $A$ fue el primer equipo de la ronda $i+1$ para hacer un movimiento en el $B$ y, a continuación, el equipo $A$ podría haber hecho el mismo movimiento en la ronda $i$ . Si repites esta lógica, podrás pasar todas las rondas aburridas al final.

Ahora, dejemos que $e$ sea el número total de aristas en $B$ . Puede haber como máximo $e$ rondas interesantes en cualquier juego de la forma $B+n{\bf z}$ . Por lo tanto, para cualquier $n>0$ juego óptimo en $B+(e+n){\bf z}$ es idéntico al juego óptimo en $B+e{\bf z}$ seguido de $n$ rondas aburridas. Esto significa que tienen el mismo resultado, por lo que la adición de $e$ copias de ${\bf z}$ es suficiente para estabilizar el tipo básico.

---

Por último, incluso cuando $p=3$ existen tablas tales que el tiempo que hay que esperar para la estabilización es arbitrariamente alto. Para cualquier $n,k\in \mathbb N$ considere el consejo $$ \langle1^n2^n\rangle+\langle3^{n-1}\rangle+k{\bf z} $$ con jugadores $1$ y $2$ se asoció, con $1$ yendo primero. Para no perder, el jugador $2$ tiene que hacer $n$ movimientos separados en el $\langle1^n2^n\rangle$ componente. Dado que cualquier movimiento del jugador $1$ en $\langle1^n2^n\rangle$ destruiría todo $2$ El jugador $1$ necesita hacer $n$ se mueve en el ${\bf z}$ componentes. Es decir, el equipo puede ganar si y sólo si $k\ge n$ .