Berlekamp switching game

The Berlekamp switching game is a mathematical problem proposed by American mathematician Elwyn Berlekamp.[1]

Rules

There is an ${\displaystyle a\times b}$ rectangular array of lights in a hall. There are ${\displaystyle ab}$ switches at the back of the hall, one for each light. At the front of the hall there are ${\displaystyle a+b}$ switches, one for each column and one for each row. Every switch at the back changes the state of the corresponding light. Every switch at the front changes the states of all lights in the corresponding row or column.

We turn on a subset ${\displaystyle S}$ of lights using switches at the back. Then we define ${\displaystyle f(S)}$ to be the minimum number of illuminated lights we can achieve using switches at the front. ${\displaystyle R_{a,b}}$ is the maximum value of ${\displaystyle f(S)}$ over all subsets ${\displaystyle S}$ of the array.

The problem is to find ${\displaystyle R_{a,b}}$ given ${\displaystyle a}$ and ${\displaystyle b}$.[2]

History

Berlekamp constructed a physical instance of this game for the case ${\displaystyle 10\times 10}$ in the Mathematics Department commons room at Bell Labs in Murray Hill.[3]

Solutions

The case of a square ${\displaystyle n\times n}$ array has been solved for ${\displaystyle n\leq 12}$ and lower bounds for ${\displaystyle R_{n,n}}$ found for ${\displaystyle n\leq 20}$.[4]

Solutions for ${\displaystyle n\times n}$

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
${\displaystyle R_{n,n}}$	0	1	2	4	7	11	16	22	27	35	43	54	≥ 60	≥ 71	≥ 82	≥ 94	≥ 106	≥ 120	≥ 132	≥ 148

Significance

The Berlekamp switching game is equivalent to the problem of the covering radius in coding theory.

Let ${\displaystyle n=ab}$ and ${\displaystyle k=a+b-1}$; then ${\displaystyle R_{a,b}}$ is the covering radius of ${\displaystyle [n,k]}$ codes, i.e. of codes with ${\displaystyle n}$ bits and ${\displaystyle k}$ dimensions.[5]

See also

• Delone set
• Lights Out (game)

References

1. Cover, Thomas M.; Gopinath, B. (1987). Open problems in communication and computation. Springer-Verlag. p. 51. ISBN 0-387-96621-8.
2. Cover, Thomas M.; Gopinath, B. (1987). Open problems in communication and computation. Springer-Verlag. p. 51. ISBN 0-387-96621-8.
3. Cover, Thomas M.; Gopinath, B. (1987). Open problems in communication and computation. Springer-Verlag. p. 51. ISBN 0-387-96621-8.
4. Carlson, Jordan; Stolarski, Daniel (October 2004). "The correct solution to Berlekamp's switching game". Discrete Mathematics. 287 (1–3): 145–150. doi:10.1016/j.disc.2004.06.015.
5. Cover, Thomas M.; Gopinath, B. (1987). Open problems in communication and computation. Springer-Verlag. p. 52. ISBN 0-387-96621-8.