1,2

Solomon W. Golomb's proof of de Bruijn's coloring theorem on a chessboard for 1 X 4 size pieces (that its impossible to color a 6 X 6 chessboard with pieces of size 1 X 4), is generalized for the torus by using M in a chessboard format. To quote Watkins, (p. 228): "However, Golomb was able to come up with a new coloring that, for example, shows that even on a torus you can't cover an m X n chessboard with 1 X 4 pieces unless 4 divides either m or n-that is, de Bruijn's theorem still holds, at least for 1 X 4 pieces." [p. 229]: And, "By the way, as de Bruijn himself originally proved, I should mention that de Bruijn's theorem holds in all higher dimensions; and so, for example, an a X b X c solid block can be constructed out of 1 X 1 X k bricks only when k divides at least one of a,b, or c.".

John J. Watkins, "Across the Board, the Mathematics of Chessboard Problems", Princeton University Press, 2004, p. 227-229.

a(1) = 1, a(2) = 21, a(n+2) = 15*a(n+1) + 18*a(n), n>2. Matrix method: Let M = the 6 X 6 matrix [1 2 1 2 1 2 / 3 4 3 4 3 4 / 1 2 1 2 1 2 / 3 4 3 4 3 4 / 1 2 1 2 1 2 / 3 4 3 4 3 4]. Then M^n *[1 0 0 0 0 0] = [a(n) q a(n) q a(n) q a(n) q], where q = a term in another sequence with the same recursion rule.

a(3) = 333 = 14*21 + 18

a(3) = 333 since M^3 * [1 0 0 0 0 0] = [333 729 333 729 333 729].

a[n_] := (MatrixPower[{{1, 2, 1, 2, 1, 2}, {3, 4, 3, 4, 3, 4}, {1, 2, 1, 2, 1, 2}, {3, 4, 3, 4, 3, 4}, {1, 2, 1, 2, 1, 2}, {3, 4, 3, 4, 3, 4}}, n].{{1}, {0}, {0}, {0}, {0}, {0}})[[1, 1]]; Table[ a[n], {n, 17}] (from Robert G. Wilson v Jun 16 2004)

Sequence in context: A091947 A016195 A016191 this_sequence A051525 A107396 A036224

Adjacent sequences: A095902 A095903 A095904 this_sequence A095906 A095907 A095908

nonn

Gary W. Adamson (qntmpkt(AT)yahoo.com), Jun 13 2004

Edited, corrected and extended by Robert G. Wilson v (rgwv(AT)rgwv.com), Jun 16 2004