

A146971


Number of weightn binary n X n matrices that yield the all1 matrix when repeatedly change a 0 having at least two 1neighbors to a 1.


0




OFFSET

1,2


COMMENTS

There is a proof that the minimum initial weight is n which can be summarized in the single word "perimeter".


REFERENCES

Erik D. Demaine, Martin L. Demaine and Helena A. Verrill, "CoinMoving Puzzles", in More Games of No Chance, edited by R. J. Nowakowski, 2002, pages 405431, Cambridge University Press. Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 2428, 2000. [From John Tromp, Nov 05 2008]
Ivars Peterson, "SlidingCoin Puzzles", Science News 163(5), Feb 01, 2003 (description of results in the above paper) [From John Tromp, Nov 05 2008]


LINKS

Table of n, a(n) for n=1..10.
PDF version of "CoinMoving Puzzles" [From John Tromp, Nov 05 2008]
Science News article [From John Tromp, Nov 05 2008]


EXAMPLE

a(3) = 14 because of there are 2,4,4 and 4 symmetrical versions of 100 010 001, 100 001 010, 101 000 100 and 101 000 010 respectively.


CROSSREFS

Sequence in context: A168658 A235347 A235352 * A246481 A048990 A089602
Adjacent sequences: A146968 A146969 A146970 * A146972 A146973 A146974


KEYWORD

nonn


AUTHOR

John Tromp, Nov 03 2008


EXTENSIONS

Additional term a(8) from Alvaro Begue's Cprogram. John Tromp, Nov 05 2008
Computed a(9) and a(1) with a 128bitboard based program, the former verifying a result from Alvaro's array based program. John Tromp, Nov 20 2008


STATUS

approved



