Juego de cambio Berlekamp

juego matematico

El juego de cambio de Berlekamp es un juego matemático propuesto por el matemático estadounidense Elwyn Berlekamp . ^[1] También se le ha llamado juego de cambio Gale-Berlekamp , ​​en honor a David Gale , quien descubrió el mismo juego de forma independiente, ^[2] o juego de luces desequilibrantes . ^[3] Se trata de 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 codificación .

Normas

El equipo para jugar consiste en una sala 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. Al otro lado de la habitación hay otro grupo de interruptores, uno para cada fila o columna de bombillas. Cada vez que se acciona cualquiera de estos interruptores, cada bombilla de la fila o columna que controla cambia de apagado a encendido o de encendido a apagado, dependiendo de su estado anterior. Al accionar más de un interruptor, el orden en el que se activan los interruptores no influye en el resultado: las mismas bombillas se encenderán al final de la secuencia de activaciones sin importar el orden en que se activen. ${\displaystyle a\times b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle ab}$ ${\displaystyle a+b}$

El juego se juega en dos rondas. En la primera ronda, el primer jugador usa los interruptores que controlan las luces individuales para encenderlas o apagarlas arbitrariamente. En la segunda ronda, el segundo jugador usa los interruptores que controlan las filas o columnas de luces, cambiando el patrón de luces establecido por el primer jugador a 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 de luces encendidas posible. 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 con computadora pueden interpretarse como la pregunta, para el juego, qué tan bien puede hacerlo el segundo jugador contra un primer jugador que juega al azar, ^[6] y por JW Moon y Leo Moser  (1966), quienes abordan teóricamente la pregunta de Gleason, 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 es cercano a . ^[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 mediante la mejor jugada del 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 como un número el mayor número de luces que se pueden lograr mediante la mejor jugada para el primer jugador . 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, en función de y , determinar su comportamiento como función, o 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 . Además, se han encontrado límites inferiores 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 a medida que . ^{[2] [5] [12]} ${\displaystyle {\tfrac {n^{2}}{2}}-\Theta (n^{3/2})}$

Complejidad computacional

Debido a que hay exponencialmente muchas opciones para qué interruptores activar, una búsqueda exhaustiva de la opción óptima no es posible para grandes , lo que plantea la cuestión 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 al azar. De manera similar, el segundo jugador puede obtener un valor cuya distancia esperada 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 polinómico que obtiene el mismo valor de solución garantizado. Una desaleatorización diferente proporciona 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 del 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 opción para el segundo jugador que deja solo multiplicado por el mínimo número 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 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 de dimensiones del espacio vectorial de dimensiones sobre el campo finito con dos elementos . Los elementos del subespacio se denominan palabras en código, y el radio de cobertura es el número más pequeño tal que cada punto esté dentro de la distancia de Hamming de una palabra en 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}$

Deja y . Para estos valores de parámetros, el espacio vectorial describe todos los patrones posibles de bombillas encendidas en el conjunto de bombillas, con una operación de suma vectorial que combina dos patrones al encender las bombillas que aparecen exactamente en uno de los dos patrones (la operación de diferencia simétrica en el juegos de bombillas encendidas). Se puede definir un subespacio lineal que consta de todos los patrones que el segundo jugador puede desactivar por completo, o de manera equivalente, de todos los patrones que el segundo jugador podría crear comenzando con un tablero que está completamente desactivado. Aunque el segundo jugador tiene opciones sobre cómo configurar el segundo banco de interruptores, este subespacio tiene elementos que le dan dimensión , porque accionar todos los interruptores del segundo jugador no tiene ningún 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 elegido por el primer jugador, con mejor juego, da un punto que se encuentra lo más alejado posible del subespacio lineal. El conjunto de bombillas cuyo estado cambia por el segundo jugador, con mejor juego, da el punto más cercano en el subespacio lineal. El conjunto de bombillas que quedan encendidas tras 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}}$

Ver también

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

Referencias

1. Sloane, Nueva Jersey (1987). "Problemas no resueltos relacionados con el radio de cobertura de los códigos". En portada, 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 ed.). 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. SEÑOR  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". Noticias de Berkeley . Universidad de California, Berkeley.
5. Brown, Thomas A.; Spencer, Joel H. (1971). "Minimización de matrices ± 1 {\displaystyle \pm 1} bajo cambios de línea". Coloquio Mathematicum . 23 : 165–171, 177. doi : 10,4064/cm-23-1-165-171 . SEÑOR  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 en matemáticas aplicadas. vol. 10. Providence, Rhode Island: Sociedad Matemática Estadounidense. págs. 175-178. SEÑOR  0114323. ${\displaystyle n}$
7. Luna, JW; Moser, L. (1966). "Un problema extremo en la teoría de matrices". Matematički Vesnik . 3(18) (37): 209–211. SEÑOR  0207570.
8. Carlson, Jordania; Stolarski, Daniel (octubre de 2004). "La solución correcta al juego de cambios de Berlekamp". Matemáticas discretas . 287 (1–3): 145–150. doi : 10.1016/j.disc.2004.06.015 . SEÑOR  2094708.
9. Sloane, Nueva Jersey (ed.). "Secuencia A005311 (Solución al juego de cambio (o juego de bombillas) de Berlekamp en un tablero n X n)". La enciclopedia en línea de secuencias enteras . Fundación OEIS.
10. Pellegrino, D.; Raposo Jr, A. (2022). "Constantes de la desigualdad Kahane-Salem-Zygmund acotadas 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 de las constantes de la desigualdad de Bennett y el juego de cambio 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) . págs. 721–728. SEÑOR  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. SEÑOR  1460721. S2CID  14313557.
14. Roth, Ron M.; Viswanathan, Krishnamurthy (2008). "Sobre la dificultad de decodificar el código Gale-Berlekamp". Transacciones IEEE sobre teoría de la información . 54 (3): 1050-1060. doi :10.1109/TIT.2007.915716. SEÑOR  2445050.
15. Karpinski, Marek ; Schudy, Warren (2009). "Esquemas de aproximación en tiempo lineal para el juego Gale-Berlekamp y problemas de minimización relacionados". En Mitzenmacher, Michael (ed.). Actas del 41º Simposio anual 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.