A005311 - OEIS

%I M1040 #37 Oct 27 2019 22:23:59

%S 0,1,2,4,7,11,16,22,27,35,43,54

%N Solution to Berlekamp's switching game (or lightbulb game) on an n X n board.

%D Brown, Thomas A.; Spencer, Joel H. Minimization of +-1 - matrices under line shifts. Colloq. Math. 23 (1971), 165--171, 177 (errata insert). MR0307944 (46 #7059). Gives asymptotic bounds, some exact values, and generalizations to an m X n board. - _N. J. A. Sloane_, Jun 29 2014

%D Komlos, J., & Sulyok, M. (1970). On the sum of elements of +-1 matrices, in Combinatorial Theory and Its Applications (P. Erdős et al., eds.), North-Holland, 721-728. Apparently gives exact solution on m X n board for m and n large. - _N. J. A. Sloane_, Jun 29 2014

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H J. Carlson and D. Stolarski, <a href="http://dx.doi.org/10.1016/j.disc.2004.06.015">The correct solution to Berlekamp's switching game</a>, Discrete Math., Vol. 287 (2004).

%H P. C. Fishburn and N. J. A. Sloane, <a href="http://dx.doi.org/10.1016/0012-365X(89)90141-6">The solution to Berlekamp's switching game</a>, Discrete Math., 74 (1989), 263-290. (Apparently our value a(10) = 34 is incorrect!)

%H N. J. A. Sloane, <a href="/A005311/a005311a.jpg">Solutions for 3 X 3 through 10 X 10 boards.</a> Note that the so-called "solution" for n=10 is incorrect.

%H N. J. A. Sloane, <a href="/A005311/a005311b.jpg">The box built by Elwyn Berlekamp in the 1960's.</a>

%e According to Calson and Stolarski, the following position with 35 lights on cannot be reduced:

%e xxx00xx000

%e xx0xx000x0

%e 0xxx00000x

%e x0x0x00x00

%e x00x0x0x00

%e 0x00xx0000

%e 000xx0x000

%e 0x0000xx00

%e 000x0000x0

%e x00000000x

%K hard,nonn,more,nice

%O 1,3

%A _N. J. A. Sloane_

%E Corrected and extended Dec 09 2003; last line of example corrected Dec 30 2004