Juego de fabricación de cajas

Un juego de construcción de cajas (a menudo llamado simplemente juego de cajas ) es un juego posicional sesgado en el que dos jugadores eligen alternativamente elementos de una familia de conjuntos disjuntos dos a dos ("cajas"). El primer jugador, llamado Constructor de Cajas , intenta elegir todos los elementos de una sola caja. El segundo jugador, llamado Rompecajas , intenta elegir al menos un elemento de todas las cajas.

El juego de la caja fue presentado por primera vez por Paul Erdős y Václav Chvátal . ^{[ 1 ]} Posteriormente fue resuelto por Hamidoune y Las-Vergnas. ^{[ 2 ]}

Un juego de caja se define por:

• Una familia de n conjuntos disjuntos por pares,${\displaystyle A_{1},\ldots ,A_{n}}$, de diferentes tamaños. Los conjuntos a menudo se denominan "cajas" y los elementos se denominan "bolas".
• Dos números enteros, p y q .

El primer jugador, el Creador de Cajas , elige p bolas (de la misma caja o de cajas diferentes). Luego, el segundo jugador, el Rompecajas , rompe q cajas. Y así sucesivamente.

BoxMaker gana si ha logrado recoger todas las bolas en al menos una caja antes de que BoxBreaker consiguiera romperla. BoxBreaker gana si ha logrado romper todas las cajas.

En general, la estrategia óptima para BoxBreaker es romper las cajas con el menor número de elementos restantes. La estrategia óptima para BoxMaker es intentar equilibrar los tamaños de todas las cajas. Al simular estas estrategias, Hamidoune y Las-Vergnas ^{[ 2 ]} hallaron una condición suficiente y necesaria para cada jugador en el juego de cajas ( p : q ).

Para el caso especial donde q = 1, cada una de las siguientes condiciones es suficiente: ^{[ 3 ] : 36–39}

• Si todas las cajas tienen el mismo tamaño k, y${\displaystyle p\cdot \sum _{i=1}^{n}{1 \over i}<k}$, entonces BoxBreaker gana el juego de cajas (p:1) (usando la estrategia obvia de romper las cajas más pequeñas). Para comparar, la condición de victoria para Breaker en un juego general sesgado ( p : q ) es: ${\displaystyle n<(q+1)^{k/p}}$. Con q =1 esto se convierte en${\displaystyle p\cdot \log _{2}{n}<k}$La demostración utiliza una función potencial. El potencial del juego antes del j -ésimo movimiento de BoxBreaker se define como:${\displaystyle {1 \over n-j+1}\sum _{i=j}^{n}c_{i}}$dónde${\displaystyle c_{i}}$es el número de elementos que quedan en la caja i .
• Si las cajas tienen diferentes tamaños${\displaystyle k_{1},\ldots ,k_{n}}$, y${\displaystyle \sum _{i=1}^{n}e^{-k_{i}/p}<{1/e}}$, entonces BoxBreaker gana el juego de la caja (p:1). Para comparar, la condición de victoria para Breaker en un juego general sesgado (p:q) es: ${\displaystyle \sum _{i=1}^{n}(1+q)^{-k_{1}/p}<{1 \over 1+q}}$. Con q=1 esto se convierte en${\displaystyle \sum _{i=1}^{n}2^{-k_{i}/p}<{1 \over 2}}$.