|
|
A005311
|
|
Solution to Berlekamp's switching game (or lightbulb game) on an n X n board.
(Formerly M1040)
|
|
1
|
|
|
0, 1, 2, 4, 7, 11, 16, 22, 27, 35, 43, 54
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
REFERENCES
|
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
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
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
EXAMPLE
|
According to Calson and Stolarski, the following position with 35 lights on cannot be reduced:
xxx00xx000
xx0xx000x0
0xxx00000x
x0x0x00x00
x00x0x0x00
0x00xx0000
000xx0x000
0x0000xx00
000x0000x0
x00000000x
|
|
CROSSREFS
|
|
|
KEYWORD
|
hard,nonn,more,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Corrected and extended Dec 09 2003; last line of example corrected Dec 30 2004
|
|
STATUS
|
approved
|
|
|
|