Juego de cambio de Berlekamp
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 el juego de cambio Gale-Berlekamp , en honor a David Gale , quien descubrió el mismo juego de forma independiente, [2] o el juego de luces de desequilibrio . [3] Se trata de un sistema de bombillas controladas por dos grupos de interruptores, en el que un jugador intenta encender muchas bombillas y el otro intenta mantener apagadas tantas como sea posible. Se puede utilizar para demostrar el concepto de radio de cobertura en la teoría de la codificación .
El equipo para jugar consiste en una sala que contiene una matriz rectangular de bombillas, de dimensiones para algunos números y . Un grupo de interruptores en un lado de la habitación controla cada bombilla individualmente. Al accionar uno de estos interruptores, su bombilla cambia de apagado a encendido o de encendido a apagado, según su estado anterior. Al otro lado de la habitación hay otro banco deinterruptores, uno para cada fila o columna de bombillas. Siempre que se activa cualquiera de estos interruptores, cada bombilla de la fila o columna que controla cambia de apagada a encendida o de encendida a apagada, según su estado anterior. Al accionar más de un interruptor, el orden en el que se accionan los interruptores no influye en el resultado: las mismas bombillas se encenderán al final de la secuencia de giros sin importar el orden en que se giren.
El juego se juega en dos rondas. En la primera ronda, el primer jugador usa los interruptores que controlan las luces individuales para encender o apagar las luces arbitrariamente. En la segunda ronda, el segundo jugador usa los interruptores que controlan 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 al final del juego como sea posible, y el objetivo del segundo jugador es tener la menor cantidad de luces encendidas como sea posible. Por lo tanto, el primer jugador debe elegir un patrón de luces para el cual el segundo jugador no puede apagar muchas luces.
Berlekamp trabajó en Bell Labs en Murray Hill, Nueva Jersey de 1966 a 1971. [4] Mientras estaba 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, en algún momento antes de 1971. [5]
Las primeras investigaciones sobre problemas relacionados incluyeron publicaciones de Andrew M. Gleason ( 1960 ), cuyos experimentos informáticos se pueden interpretar como preguntas, 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 opciones del primer jugador, en el límite de los tamaños de tablero de juego grandes, el valor óptimo del juego se acerca a . [7]
