Tres contra el diablo: un juego combinatorio

Question

Un equipo de tres pecadores juega un partido contra el diablo. Antes de la partida, se ponen de acuerdo sobre la estrategia; luego, entran en tres salas separadas y no hay más comunicación entre ellos. El juego en cada sala sigue las mismas reglas, como se describe a continuación.

Una jugada consiste en elegir algunos números del conjunto $\{1,\dots,N\}$ donde $N$ es un número natural fijo. Un número sólo puede elegirse una vez; así, los dos jugadores de la sala, el pecador y el diablo, se reparten un conjunto finito, como en el tres en raya o el hexágono. El diablo se mueve primero y elige dos números en cada turno. El pecador se mueve en segundo lugar y elige tres números en cada turno. El juego continúa hasta que todos los $N$ números han sido elegidos.

Los pecadores ganan si hay al menos un número que es elegido por todos ellos; en caso contrario, gana el diablo.

Pregunta: ¿Los pecadores tienen una estrategia ganadora si $N$ es lo suficientemente grande?

1. No nos interesan las estrategias aleatorias. Una estrategia ganadora es una determinista estrategia que es segura para ganar contra el juego arbitrario del diablo.

2. No sé si hay una respuesta afirmativa para $N=\omega$ ni si una respuesta afirmativa para $N=\omega$ implicaría una respuesta afirmativa para algún finito $N$ .

3. Se puede hacer la misma pregunta para equipos más grandes, pero un equipo de tres personas es el caso más pequeño e interesante. Un equipo de dos gana automáticamente si $N\ge5$ .

4. El diablo tiene que moverse primero, o si no es una victoria trivial para los pecadores.

5. Le site $3$ -a- $2$ juego sesgado ( $3$ se mueve para los pecadores, $2$ para el diablo) es el caso interesante más sencillo. El $1$ -a- $1$ es una victoria fácil para el diablo, incluso contra un equipo de dos. Los pecadores pueden ganar el $2$ -a- $1$ versión (con equipos de cualquier tamaño finito) si N es lo suficientemente grande, pero eso no es completamente trivial.

6. Llamé a los jugadores del equipo "pecadores" porque no sabía cómo llamarlos; "hombres" o "mujeres" sería sexista, "personas" o "humanos" suena demasiado rebuscado. Supongo que "mortales" funcionaría, pero no se me había ocurrido hasta ahora.

7. Utilicé la etiqueta combinatorial-game-theory porque me pareció correcta, pero veo que la explicación oficial dice que es para juegos de información perfecta. ¿Fue eso un pecado?

Editar para aclarar: A juzgar por los comentarios, mis imágenes poéticas sobre el Príncipe de las Tinieblas están confundiendo a la gente. No importa lo que el diablo sabe o no sabe, porque estoy pidiendo estrategias que ganan contra juego arbitrario del diablo En otras palabras, en el El peor de los casos .

Si te sirve de ayuda, puedes imaginar que el diablo, en lugar de jugar con malicia, está haciendo movimientos aleatorios . Los jugadores tienen entonces una excelente oportunidad de ganar. La cuestión es si, para algunos $N$ hay una estrategia que gana con probabilidad uno .

Para decirlo de forma más prosaica, dejemos que $B=\{1,\dots,N\}$ y definir un estrategia como una función $\sigma:2^B\rightarrow2^B$ tal que, para cada $X\subseteq B$ tenemos $\sigma(X)\subseteq X$ y $|\sigma(X)|=\min\{3,|X|\}$ . La cuestión es si, para un tamaño suficientemente grande $N$ existen estrategias $\sigma_1,\sigma_2,\sigma_3$ de manera que, siempre que $S_i$ es el conjunto de números obtenidos por el pecador en un $\sigma_i$ -juego compatible (sea lo que sea que eso signifique--la definición se deja como ejercicio para el lector), tenemos $S_1\cap S_2\cap S_3\ne\emptyset$ .

P.D. Respuesta más corta: Sí, el diablo conoce las estrategias de los pecadores.

Editado de nuevo para mayor aclaración : Creo que el siguiente replanteamiento es equivalente a la pregunta original:

Pregunta (reformulada): ¿Existe (para algunos $N$ ) familias $\mathcal W_1,\mathcal W_2,\mathcal W_3\subseteq2^{\{1,\dots,N\}}$ tal que (1) el jugador $i$ tiene una estrategia que garantiza que obtendrá todos los elementos de algún conjunto $W_i\in\mathcal W_i$ y (2) si $W_i\in\mathcal W_i$ para $i=1,2,3$ entonces $W_1\cap W_2\cap W_3\ne\emptyset$ ? (Como antes, el Adversario va primero, y elige dos números en cada turno; el Jugador va segundo, y elige tres números en cada turno).

Supongo que debería haberlo dicho así desde el principio, en lugar de confundir la cuestión tratando de convertirla en un problema de la historia. Lo siento.

Preguntas de seguimiento sobre la respuesta de Zackkenyon:

Todavía no he entrado en los detalles. Tengo una pregunta a grandes rasgos sobre qué es lo que estás probando.

Su prueba comienza en hablar de un número $k$ y una partición en conjuntos $S_{k,i}$ sin explicar de dónde vienen ni qué tienen que ver. Primero tengo que introducir alguna notación. Luego intentaré exponer lo que creo que están haciendo, para que me digan si tengo razón o no.

A estrategia para los pecadores es un triple ordenado $\sigma=(\sigma_1,\sigma_2.\sigma_3)$ donde $\sigma_i$ le dice al pecador $i$ cómo jugar en la sala $i$ . Dado un número natural $k$ y una partición $\mathcal S=\{S_1,S_2,\dots\}$ de $[N]$ en $k$ -conjuntos de elementos, diré que una estrategia $\sigma=(\sigma_1,\sigma_2,\sigma_3)$ tiene propiedad $Z(k,\mathcal S)$ si garantiza que, independientemente de cómo juegue el diablo, habrá algún $i$ tal que cada número de $S_i$ es elegido por el pecador 3, mientras que al menos un número de $S_i$ es elegido tanto por el pecador 1 como por el pecador 2.

Evidentemente, si la estrategia $\sigma$ tiene propiedad $Z(k,\mathcal S)$ para algunos naturales $k$ y alguna partición $\mathcal S$ en $k$ -conjuntos de elementos, entonces $\sigma$ es una estrategia ganadora. Tal vez se me escapa algo obvio, pero no veo ninguna razón para que lo contrario se sostenga; excepto, por supuesto, que se sostenga vacuamente si hay son no hay estrategias ganadoras. De entrada, me parece que lo que estás haciendo es demostrar que ninguna estrategia puede tener la propiedad $Z(k,\mathcal S)$ .

¿Lo he entendido bien? ¿Demuestra tu argumento (I) que los pecadores no tienen ningún tipo de estrategia ganadora, o sólo muestra (II) que un cierto tipo de estrategia natural (en la que la mayoría de la gente piensa primero cuando trata de demostrar la afirmativa) no puede existir, dejando abierta la posibilidad de que algún tipo de estrategia más exótica haga el truco? En el caso (I) me gustaría ver alguna explicación de cómo se deduce eso de lo que has escrito, o si hay alguna parte más del argumento que no has escrito. En el caso (II), es una buena respuesta parcial, pero por supuesto no resuelve la cuestión.

Para aclarar la cuestión, voy a intentar definir en general lo que significa un triple $\sigma=\sigma_1,\sigma_2,\sigma_3$ para ser una estrategia ganadora para los pecadores, por lo que podemos compararlo con (lo que entiendo que es) su enfoque. Primero vamos a considerar lo que ocurre en la sala 3: utilizando la estrategia $\sigma_3$ el pecador 3 adquiere un conjunto S de tamaño $2N/5$ . (No es malo suponer que $N$ divisible por $5$ .) Sea $\mathcal S=\{S_1,S_2,\dots\}$ sea la colección de todos los conjuntos obtenidos de esta manera, con el pecador 3 utilizando $\sigma_3$ contra todas las posibles jugadas del diablo. Pecador 3 está garantizado para conseguir todos los elementos de unos $S_i$ pero que $S_i$ que consigue se lo lleva el diablo. Claramente, entonces, para que los pecadores tengan una victoria forzada, $\sigma_1$ y $\sigma_2$ tienen que garantizar que para cada índice $i$ hay al menos un elemento de $S_i$ que es elegido tanto por el pecador 1 como por el pecador 2.

Esto es algo así como su $Z(k,\mathcal S)$ con $k=2N/5$ La gran diferencia es que el $S_i$ no son disjuntos, lo que parece confundir mucho la cuestión. ¿Funciona su argumento si el $S_i$ no son disjuntos?

Answer 1

Este es un problema de lo más intrigante y me llevó muchas, muchas, muchas horas de pensamiento para resolverlo, incluso escribí un script para entenderlo mejor.

Es posible que los pecadores (jugadores) ganen siempre. El número de jugadores que juegan es irrelevante y el número de números que eligen por turno es irrelevante siempre que los jugadores consigan elegir más números que el diablo. En otras palabras:

Teorema. Sea $n,m,k\in\mathbb{N}$ tal que $n>m$ , entonces a $$n\text{-to-}m\text{ bias game & with }k\text{ players playing,}$$ tiene una solución ganadora para los jugadores.

Para mostrar cómo funciona esta solución, vamos a demostrar primero el $3$ -a- $2$ esquema de sesgo con $3$ jugadores que juegan. Deje que $N=10^{2101}$ y $P=\{1,\ldots,10^{2101}\}$ sea un conjunto grande.

El jugador 1 sólo tiene un trabajo, elige un número en cada uno de los conjuntos $\{3n+1,3n+2,3n+3\}$ Esto se puede hacer fácilmente, ya que el diablo sólo puede recoger hasta dos números a la vez.

Así, el jugador 2 se encuentra ahora con $N'=10^{2101}/3$ conjuntos, $P'=\{A_1,\ldots, A_{N'}\}$ . Sea $$P'_1=\{A_1,\ldots,A_{1000}\} \\ P'_2=\{A_{1001},\ldots,A_{2000}\} \\ \vdots \\ P'_{10^{2101}/3000}=\{A_{10^{2101}/3-999},\ldots,A_{N'}\}$$

tal que cada conjunto $A_i$ , es de tamaño tres y en cada juego, $A_i$ El jugador 1 ha elegido al menos un número. Ahora el diablo elige dos números, en digamos $P_i'$ y $P_j'$ cualquiera que sea el número, borre los conjuntos que contienen esos números de $P_i'$ y $P_j'$ . Ahora elige dos números de dos conjuntos diferentes que quedan en $P'_i$ y $P'_j$ Para su tercera opción, elija un número de un conjunto diferente al de los dos primeros números, ya sea de $P'_i$ o $P'_j$ el que tenga menos conjuntos de los que ha elegido números. Para un número fijo de $i$ , $P'_i$ Sin embargo, con el tiempo se eliminará alrededor del 80% de sus conjuntos (porque el diablo habrá elegido entre esos conjuntos), $P'_i$ consistirá ahora en unos 200 conjuntos que contienen cada uno un número que el jugador 2 ha elegido. Continuamos de esta manera hasta $P'_i$ contiene alrededor de $$1000\cdot (.2)^3 \approx 8$$ conjuntos en los que el jugador 2 habrá elegido todos los números y, por tanto, el jugador 1 y el jugador 2 compartirán un número en uno de los conjuntos en $P'_i$ .

Finalmente se presentará el Jugador 3, $R=\{R_1,\ldots,R_{10^{2101}/3000}\}$ con $$R_1=\{1,\ldots,3000\} \\ R_2=\{3001,\ldots,6000\} \\ \vdots $$ una colección de unos $10^{2101}/3000$ conjuntos y el único conocimiento que tiene el Jugador 3, es que el Jugador 1 y el Jugador 2 comparten un elemento en cada $R_i$ . El diablo va primero y escoge dos números; cualquiera de los números que el diablo escoja, borra esos conjuntos de $R$ . Por ejemplo, supongamos que el diablo escoge $1$ y a continuación eliminar todo el conjunto $R_1=\{1,\ldots,3000\}$ de $R$ . Ahora, de los conjuntos restantes (que el diablo aún no ha tocado) elige tres números, uno de cada uno de los tres conjuntos en $R$ . Fase 2: El diablo elegirá ahora dos números más de dos conjuntos más, quizás de conjuntos que hayas elegido, quizás de conjuntos que no hayas elegido, sea cual sea el caso, borra esos conjuntos de $R$ y vuelve a elegir de los conjuntos restantes (que el diablo no ha tocado) tres números más de conjuntos que no hayas elegido ya. Como siempre tiene una jugada más que el diablo, entonces cuando todos los conjuntos en $R$ se han agotado, has tirado como mucho el 80% de los conjuntos (ya que el diablo eligió de ellos); sin embargo, los conjuntos restantes tendrán todos un número en ellos que tú has elegido y ningún número que el diablo haya elegido. Definimos los conjuntos restantes como $R'$ . De nuevo, $R'$ es aproximadamente un 20% del tamaño de $R$ . Ahora repetimos el proceso en $R'$ y llegar a $R''$ un conjunto del 20% del tamaño de $R'$ pero ahora cada conjunto en $R''$ tiene dos elementos que has elegido y el diablo no ha elegido ninguno de los números de esos conjuntos. Con este patrón, un cálculo de $$\frac{10^{2101}}{3000}\cdot (.2)^{3000} \approx 4$$ muestra que habrá alrededor de $4$ conjuntos restantes que el jugador 3 habrá elegido todos los números en y el diablo no ha elegido ninguno. Así, los tres jugadores habrán elegido al menos un número en común.

Se puede ver que se necesitan grandes números para asegurar que se llegue a una solución ganadora. Supongamos por un momento que un cuarto jugador se uniera a nuestro grupo de tres jugadores, ¿ahora cómo proceder para asegurar que todavía ganen?

Todo el proceso anterior, asegura que los tres primeros jugadores compartirán un número en el conjunto $\{1,\ldots,10^{2101}\}$ . Repetimos este proceso con otro conjunto $\{10^{2101}+1,\ldots,2\cdot 10^{2101}\}$ . El jugador 3 tendrá dos juegos para hacer malabares a $A$ y $B$ que contienen cada uno $10^{2101}/3000$ conjuntos. El diablo puede jugar completamente en $A$ o jugar completamente en $B$ o puede elegir jugar en cada set. El jugador 3 simplemente tiene que asegurarse de que $A$ y $B$ perder conjuntos a un ritmo igual. Si el jugador 3 centra toda su atención en $A$ y el diablo sigue jugando en $B$ , entonces el jugador 3 acabará con un 0% de conjuntos útiles en $B$ . Para que esto no ocurra el jugador 3 debe jugar en $A$ si el diablo juega en $A$ y debería jugar en $B$ en el diablo juega en $B$ . Si el diablo elige un número en $A$ y un número en $B$ , entonces el jugador 3 debe elegir un número en $A$ y un número en $B$ y luego utilizar su tercera opción en el conjunto que tiene (actualmente) el menor número de "conjuntos buenos".

Esto nos dará dos conjuntos, $\{1\dots,10^{2101}\}$ y $\{10^{2101}+1,\ldots,2\cdot 10^{2101}\}$ en el que los tres primeros jugadores comparten un número en esos conjuntos. ¿Cuántos conjuntos necesitaremos realizar así hasta que el jugador 4 tenga suficientes conjuntos? Pues queremos $N$ conjuntos tales que: $$N\cdot (.2)^{10^{703}}>1.$$ Por lo tanto, un &%#@ing &*#@ número de juegos.

Pero es posible y entonces el jugador 4 se presentará con $N$ conjuntos que tienen cada uno $10^{2101}$ números tales que en cada conjunto haya al menos un número que compartan los tres primeros jugadores. Y así, el jugador 4 puede continuar de la misma manera que el jugador 3.

Si alguien conoce una forma más fácil de describir mi método, por favor, hágalo saber a la comunidad.

Answer 2

Todavía no está probado, pero es esperanzador: Los pecadores no pueden ganar el juego.

El argumento hasta ahora.

La afirmación "el pecador 3 ha ganado la partida"

equivale a la afirmación

"De todos los números que el pecador 3 ha elegido, uno de ellos era un número que tanto el pecador 1 como el 2 han elegido".

asimismo la afirmación "el pecador 3 sabe que ha ganado la partida" es equivalente a la afirmación "el pecador 3 sabe que de todos los números que ha elegido, uno de ellos era un número que el pecador 1 y el pecador 2 eligieron"

Si los pecadores tienen una estrategia absolutamente ganadora, entonces el pecador 3 sabe que ha ganado la partida.

Para cada k, podemos dividir el conjunto de opciones en conjuntos disjuntos con k elementos cada uno, llamando a tal partición $\{S_{k,i}\}_{i\in [1,N/i]}$ .

o más bien existe una prueba de la afirmación

para una estrategia determinada $K=(\sigma_1,\sigma_2,\sigma_3)$ , $\exists$ $x$ en $S_{k,i}$ El pecador 1 ha elegido $x$ y el pecador 2 ha elegido $x$

y el pecador tres posee todo el número en ese $S_{k,i}$

si para una estrategia dada K, existe una prueba de $\exists x \in S_{k,i}$ Llama a este tipo de $S_{k,i}$ a solapamiento k garantizado .

thm 1: $\forall k$ hay como máximo $2^{(\lfloor k/2\rfloor +1)}-2$ de la $S_{k,i}$ tal que para cada uno de ellos hay un solapamiento k garantizado .

Un pecador sostiene un mayoría de los números en $S_{k,i}$ si ha elegido $\lfloor{k/2}\rfloor+1$ de ellos.

Un pecador sostiene un plomo en un $S_{k,i}$ si en cualquier punto en el juego, el pecador ha seleccionado más elementos de $S_{k,i}$ que el diablo.

Si un pecador tiene la mayoría, entonces el pecador tiene la ventaja. Asimismo, el conjunto de $S_{k,i}$ para una estrategia dada en la que el pecador puede demostrar que tiene la mayoría es un subconjunto de la $S_{k,i}$ en la que puede demostrar que tiene una ventaja.

Lema 1: $\forall k$ cada uno de los pecadores puede demostrar que tiene una ventaja en no más de $2^{\lfloor k/2\rfloor}-1$ de la $S_{k,i}$ .

para un estado dado del juego, que la secuencia $\{D_n\}$ consulte el $S_{k,i}$ en el que el diablo ha elegido n números más que el jugador, y tal que el jugador no tiene ventaja.

que el conjunto $X$ consulte el $S_{k,i}$ en la que el jugador tiene una ventaja.

separamos la estrategia del diablo en rondas. La estrategia del diablo es simple, en la ronda $m$ el diablo seguirá moviéndose mientras haya papeleras que haya tomado menos de $m$ bolas de, y para el que el pecador no tiene una pista.

1 Dejar $Q_i = \sum_{n}{\# D_n*(n+1)}$ después de la primera ronda.
2 por cada bola que el diablo saque de una papelera en la ronda $i$ , $Q_i$ aumenta en 1.
3 por cada balón que el jugador saque de sone $D_n$ en redondo $i$ , $Q_i$ disminuye en 1.
4 $Q_i$ disminuye por el número de bolas que el diablo recogió en la ronda i dividido por 2.
5 $Q_0$ es igual al número de bins = $2^{\lfloor k/2\rfloor}$ .
6 si $Q_{\lfloor k/2\rfloor}$ es positivo, entonces el diablo tiene la mitad, o 1 menos que la mayoría en algunos $S_k,i$ para el cual el pecador no tiene una pista, en este último caso el diablo se mueve aquí inmediatamente después de completar la ronda $\lfloor k2\rfloor$ .
7 $Q_i\le Q_{i+1}*2 \Rightarrow Q_0\le Q_{\lfloor k/2\rfloor}*2^{\lfloor k/2\rfloor}\Rightarrow Q_{\lfloor k/2\rfloor} \ge 1$

Definir un par-mayoritario para ser un $S_{k,i}$ en la que los pecadores 1 y 2 han seleccionado entre ellos $k+1$ números. Se deduce que si tienen una mayoría de pares, entonces uno de ellos tiene la mayoría.

Corrolario 1: los pecadores pueden garantizar una mayoría de pares o una ventaja como máximo $2^{\lfloor k/2\rfloor+1}-2$ de la $S_{k,i}$ .

Lema 2: si los pecadores 1 y 2 no tienen una mayoría de pares o una ventaja en un $S_{k,i}$ entonces no es un solapamiento k garantizado.

esto es a lo sumo el juego más simple 1-1 con dos jugadores.

Invocamos algunas de las habilidades especiales del diablo para una prueba rápida. El diablo juega a los dos juegos simultáneamente. hace su primera elección $\alpha$ en su partida con el pecador 1 de forma arbitraria, luego juega lo que el jugador 1 haya jugado en último lugar en su partida con el jugador 2 y viceversa hasta que el jugador 2 seleccione $\alpha$ . El diablo repite este proceso hasta que no hay más números, y el jugador 1 y el jugador 2 no tienen una superposición.

esto demuestra el tema 1

Tema 2: dado $3^{k-3}+1$ o 2 si $k<3$ garantizado k-overlaps, el diablo puede impedir que el pecador 3 seleccione todos los valores en cualquiera de ellos.

Realmente no he pensado en una forma sucinta de demostrar esto, pero está claro por la estrategia del pecador 3 para lograr esta condición. que implica la selección de 1 número de cada conjunto, luego la selección de uno del tercio de estos del que el diablo no pudo seleccionar uno, luego de nuevo del siguiente tercio y así sucesivamente, hasta que sólo quedan tres en un conjunto, momento en el que el pecador selecciona los tres.

desde $(3^{k-3}+1\ or\ 2) \ge 2^{\lfloor k/2\rfloor+1}-2$ para todos $k\ne 4$ y hay cero solapamientos garantizados para k=4. (similar a la prueba del lema 2). No existe ninguna estrategia K tal que haya una prueba de la afirmación $S_{k,i}$ contiene un elemento que el pecador 1 y el pecador 2 han elegido, y que el pecador 3 ha elegido todos los elementos de esa $S_{k,i}$ . por lo tanto, no existe ninguna estrategia ganadora. $\square$

Answer 3

No creo que haya una estrategia ganadora tal y como se describe el juego. Si el diablo elige x número de cartas de y número de pecadores, entonces existe una solución cuando los pecadores pueden elegir xy-1 números. Este es un problema de encasillamiento. Finalmente, si los pecadores pueden elegir xy-1 números la estrategia ganadora es elegir los números más bajos que el diablo no elige.