Juego de cambio de Berlekamp

Juego matemático

El juego de conmutación de Berlekamp es un juego matemático propuesto por el matemático estadounidense Elwyn Berlekamp . ^[1] También se lo ha llamado juego de conmutación de Gale-Berlekamp , ​​en honor a David Gale , quien descubrió el mismo juego de forma independiente, ^[2] o juego de luces desequilibradas . ^[3] Implica un sistema de bombillas controladas por dos bancos de interruptores, en el que un jugador intenta encender muchas bombillas y el otro intenta mantener apagadas la mayor cantidad posible. Puede utilizarse para demostrar el concepto de radio de cobertura en la teoría de la codificación .

Normas

El equipo para jugar el juego consiste en una habitación que contiene una serie rectangular de bombillas, de dimensiones para algunos números y . Un banco de interruptores en un lado de la habitación controla cada bombilla individualmente. Al accionar uno de estos interruptores, la bombilla cambia de apagada a encendida o de encendida a apagada, dependiendo de su estado anterior. En el otro lado de la habitación hay otro banco de interruptores, uno para cada fila o columna de bombillas. Siempre que se acciona cualquiera de estos interruptores, cada bombilla en la fila o columna que controla cambia de apagada a encendida o de encendida a apagada, dependiendo de su estado anterior. Al accionar más de un interruptor, el orden en que se accionan los interruptores no hace ninguna diferencia en el resultado: las mismas bombillas se encenderán al final de la secuencia de accionados sin importar en qué orden se accionan. ${\displaystyle a\times b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle ab}$ ${\displaystyle a+b}$

El juego se desarrolla en dos rondas. En la primera ronda, el primer jugador utiliza los interruptores que controlan las luces individuales para encenderlas o apagarlas arbitrariamente. En la segunda ronda, el segundo jugador utiliza los interruptores que controlan las filas o columnas de luces, cambiando el patrón de luces establecido por el primer jugador por otro patrón (o, posiblemente, dejándolo sin cambios). El objetivo del primer jugador es tener tantas luces encendidas como sea posible al final del juego, y el objetivo del segundo jugador es tener la menor cantidad posible de luces encendidas. Por lo tanto, el primer jugador debe elegir un patrón de luces para el cual el segundo jugador no pueda apagar muchas luces.

Historia

Berlekamp trabajó en Bell Labs en Murray Hill, Nueva Jersey, de 1966 a 1971. ^[4] Mientras estuvo allí, construyó una instancia física de este juego para el caso en la sala común del Departamento de Matemáticas. ^{[1] [2]} David Gale también inventó el juego de forma independiente, algún tiempo antes de 1971. ^[5] ${\displaystyle 10\times 10}$

Las primeras investigaciones sobre problemas relacionados incluyeron publicaciones de Andrew M. Gleason  (1960), cuyos experimentos de computadora pueden interpretarse como una pregunta, para el juego, qué tan bien puede jugar el segundo jugador contra un primer jugador que juega aleatoriamente, ^[6] y de JW Moon y Leo Moser  (1966), quienes abordan la pregunta de Gleason teóricamente, mostrando que para casi todas las elecciones del primer jugador, en el límite de tamaños de tablero de juego grandes, el valor óptimo del juego está cerca de . ^[7] ${\displaystyle 15\times 15}$ ${\displaystyle {\tfrac {1}{2}}n^{2}}$

Análisis

Matemáticamente, se pueden describir las luces encendidas por el movimiento del primer jugador como un conjunto , y el número más pequeño de luces que se puede lograr con la mejor jugada para el segundo jugador como un número . La mejor jugada para el primer jugador es elegir un conjunto que maximice . Por lo tanto, se puede describir el número más grande de luces que se puede lograr con la mejor jugada para el primer jugador como un número . Más allá de la cuestión de cómo jugar bien en un juego individual, una cuestión más amplia que ha sido objeto de investigación matemática es caracterizar el valor de en general, como una función de y , para determinar su comportamiento como una función, o para calcular su valor para tantas combinaciones de y como sea posible. ${\displaystyle S}$ ${\displaystyle f(S)}$ ${\displaystyle S}$ ${\displaystyle f(S)}$ ${\textstyle R_{a,b}=\max _{S}f(S)}$ ${\displaystyle R_{a,b}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$

Se ha resuelto el caso de una matriz cuadrada para . Además, se han encontrado límites inferiores para para . ^{[8] [9] [10] [11]} Estos números son: ${\displaystyle n\times n}$ ${\displaystyle n\leq 12}$ ${\displaystyle R_{n,n}}$ ${\displaystyle n\leq 20}$

Asintóticamente , estos números crecen como . ^{[2] [5] [12]} ${\displaystyle {\tfrac {n^{2}}{2}}-\Theta (n^{3/2})}$

Complejidad computacional

Debido a que hay exponencialmente muchas opciones para elegir qué interruptores activar, no es posible realizar una búsqueda exhaustiva de la opción óptima para juegos grandes , lo que plantea la pregunta de qué tan bien pueden jugar este juego los jugadores con limitaciones computacionales. ${\displaystyle n}$

El primer jugador puede hacer que el valor esperado del juego sea jugando aleatoriamente. De manera similar, el segundo jugador puede obtener un valor cuya distancia esperada desde es jugando aleatoriamente; este valor puede ser mayor o menor que , pero si es mayor, el segundo jugador puede activar todos los interruptores de fila para obtener un valor que sea menor en la misma cantidad. ^{[2] [5] [12]} Esta estrategia aleatoria para el segundo jugador se puede hacer no aleatoria utilizando el método de probabilidades condicionales , dando un algoritmo de tiempo polinomial que obtiene las mismas garantías de valor de solución. Una desaleatorización diferente da un algoritmo paralelo en la clase de complejidad NC . ^[13] ${\displaystyle {\tfrac {n^{2}}{2}}-O(n^{3/2})}$ ${\displaystyle {\tfrac {n^{2}}{2}}}$ ${\displaystyle \Omega (n^{3/2})}$ ${\displaystyle {\tfrac {n^{2}}{2}}}$

Encontrar la elección óptima para el segundo jugador en el juego, una vez que el primer jugador ha elegido qué bombillas encender, es un problema NP-difícil . ^[14] Sin embargo, existe un esquema de aproximación de tiempo polinomial para el juego que puede encontrar una elección para el segundo jugador que deja solo veces el número mínimo posible de bombillas encendidas, para cualquier , en el tiempo . ^[15] ${\displaystyle n\times n}$ ${\displaystyle (1+\varepsilon )}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle O(n^{2})+2^{O(1/\varepsilon ^{2})}}$

Conexión con la teoría de la codificación

El juego de conmutación de Berlekamp se puede utilizar en la teoría de la codificación como una demostración del radio de cobertura de un determinado código lineal binario . Un código lineal binario de longitud y dimensión se define como un subespacio lineal -dimensional del espacio vectorial -dimensional sobre el cuerpo finito con dos elementos , . Los elementos del subespacio se denominan palabras de código y el radio de cobertura es el número más pequeño tal que cada punto de está dentro de la distancia de Hamming de una palabra de código. ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle \mathbb {F} _{2}^{n}}$ ${\displaystyle \mathbb {F} _{2}}$ ${\displaystyle r}$ ${\displaystyle \mathbb {F} _{2}^{n}}$ ${\displaystyle r}$

Sea y . Para estos valores de parámetros, el espacio vectorial describe todos los patrones posibles de bombillas encendidas en la matriz de bombillas, con una operación de adición vectorial que combina dos patrones encendiendo las bombillas que aparecen exactamente en uno de los dos patrones (la operación de diferencia simétrica en los conjuntos de bombillas encendidas). Se puede definir un subespacio lineal que consiste en todos los patrones que el segundo jugador puede apagar por completo, o equivalentemente en todos los patrones que el segundo jugador podría crear comenzando con un tablero que está completamente apagado. Aunque el segundo jugador tiene opciones sobre cómo configurar el segundo banco de interruptores, este subespacio tiene elementos, lo que le da dimensión , porque encender todos los interruptores del segundo jugador no tiene efecto en el patrón de bombillas encendidas. ${\displaystyle n=ab}$ ${\displaystyle d=a+b-1}$ ${\displaystyle \mathbb {F} _{2}^{n}}$ ${\displaystyle a\times b}$ ${\displaystyle 2^{a+b}}$ ${\displaystyle 2^{a+b-1}}$ ${\displaystyle a+b-1}$

Entonces es el radio de cobertura de este código. El conjunto de bombillas encendidas elegidas por el primer jugador, con mejor juego, da un punto de que está lo más alejado posible del subespacio lineal. El conjunto de bombillas cuyo estado cambia el segundo jugador, con mejor juego, da el punto más cercano en el subespacio lineal. El conjunto de bombillas que permanecen encendidas después de estas elecciones son aquellas cuyo número define la distancia de Hamming entre estos dos puntos. ^[1] ${\displaystyle R_{a,b}}$ ${\displaystyle \mathbb {F} _{2}^{n}}$

Véase también

• Lights Out (juego) , un rompecabezas diferente que implica apagar bombillas mediante interruptores que controlan varias bombillas.

Referencias

1. Sloane, NJA (1987). "Problemas no resueltos relacionados con el radio de cobertura de los códigos". En Cover, Thomas M. ; Gopinath, B. (eds.). Problemas abiertos en comunicación y computación . Nueva York: Springer. págs. 51–56. doi :10.1007/978-1-4612-4808-8_11.
2. Spencer, Joel (1994). "Conferencia 6: Caos a partir del orden". Diez conferencias sobre el método probabilístico . Serie de conferencias regionales CBMS-NSF sobre matemáticas aplicadas. Vol. 64 (segunda edición). Filadelfia, Pensilvania: Sociedad de matemáticas industriales y aplicadas. págs. 45–50. doi :10.1137/1.9781611970074. ISBN 0-89871-325-0.Señor 1249485  .
3. Araújo, Gustavo; Pellegrino, Daniel (2019). "Un problema de cambio de permutación de Gale–Berlekamp en dimensiones superiores". Revista Europea de Combinatoria . 77 : 17–30. arXiv : 1801.09194 . doi :10.1016/j.ejc.2018.10.007. MR  3872901. S2CID  57760841.
4. Sanders, Robert (18 de abril de 2019). "Elwyn Berlekamp, ​​teórico de juegos y pionero de la codificación, muere a los 78 años". Berkeley News . Universidad de California, Berkeley.
5. Brown, Thomas A.; Spencer, Joel H. (1971). "Minimización de matrices ± 1 {\displaystyle \pm 1} bajo desplazamientos de línea". Colloquium Mathematicum . 23 : 165–171, 177. doi : 10.4064/cm-23-1-165-171 . MR  0307944.
6. Gleason, Andrew M. (1960). "Un problema de búsqueda en el cubo". En Bellman, Richard ; Hall, Marshall Jr. (eds.). Análisis combinatorio . Actas de simposios sobre matemáticas aplicadas. Vol. 10. Providence, Rhode Island: American Mathematical Society. págs. 175–178. MR  0114323. ${\displaystyle n}$
7. Moon, JW; Moser, L. (1966). "Un problema extremal en la teoría de matrices". Matematički Vesnik . 3(18) (37): 209–211. MR  0207570.
8. Carlson, Jordan; Stolarski, Daniel (octubre de 2004). "La solución correcta al juego de conmutación de Berlekamp". Matemáticas discretas . 287 (1–3): 145–150. doi : 10.1016/j.disc.2004.06.015 . MR  2094708.
9. Sloane, N. J. A. (ed.). "Secuencia A005311 (Solución al juego de conmutación de Berlekamp (o juego de la bombilla) en un tablero n X n)". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.
10. Pellegrino, D.; Raposo Jr, A. (2022). "Constantes de la desigualdad de Kahane–Salem–Zygmund acotada asintóticamente por 1". Revista de análisis funcional . 282 (2): 109293. arXiv : 2006.12892 . doi :10.1016/j.jfa.2021.109293. S2CID  231895733.
11. Pellegrino, D.; Raposo Jr, A. (2021). "Límites superiores para las constantes de la desigualdad de Bennett y el juego de conmutación de Gale-Berlekamp". arXiv : 2111.00445v3 [math.CO].
12. Komlós, J. ; Sulyok, M. (1970). "Sobre la suma de elementos de matrices". Teoría combinatoria y sus aplicaciones, II (Proc. Colloq., Balatonfüred, 1969) . pp. 721–728. MR  0299500. ${\displaystyle \pm 1}$
13. Berger, Bonnie (1997). "El método del cuarto momento". Revista SIAM de Computación . 26 (4): 1188–1207. doi :10.1137/S0097539792240005. MR  1460721. S2CID  14313557.
14. Roth, Ron M.; Viswanathan, Krishnamurthy (2008). "Sobre la dificultad de decodificar el código Gale-Berlekamp". IEEE Transactions on Information Theory . 54 (3): 1050–1060. doi :10.1109/TIT.2007.915716. MR  2445050.
15. Karpinski, Marek ; Schudy, Warren (2009). "Esquemas de aproximación de tiempo lineal para el juego de Gale–Berlekamp y problemas de minimización relacionados". En Mitzenmacher, Michael (ed.). Actas del 41.º Simposio Anual de la ACM sobre Teoría de la Computación, STOC 2009, Bethesda, MD, EE. UU., 31 de mayo - 2 de junio de 2009 . ACM. págs. 313–322. arXiv : 0811.3244 . doi :10.1145/1536414.1536458.