
Tiling the plane with checkerboard patterns
Posted:
Jul 6, 2010 4:06 PM


Here is an interesting and unsolved(!) problem, somewhat related to geometry. Insightful results would be worth publishing.
Consider an nxn checkerboard whose squares are colored black or white at random. There are exactly 2^(n^2) such checkerboards. For example, when n=2, we get the 2^(2^2) = 16 checkerboards: 0,0 0,0 0,0 0,0 0,1 0,1 0,1 0,1 0,0 0,1 1,0 1,1 0,0 0,1 1,0 1,1 1,0 1,0 1,0 1,0 1,1 1,1 1,1 1,1 0,0 0,1 1,0 1,1 0,0 0,1 1,0 1,1
where I have used 0 and 1 to represent black and white. I will refer to these as checkerboards #1 to #16, in the order they are written, from left to write, from top to bottom.
Now, we take one of these checkerboards and use it to tile the plane by laying copies of it sidebyside horizontally and vertically. Thus the entire twodimensional plane turns into an infinite checkerboard with a repeating pattern. I will call this a "wallpaper pattern" or "wallpaper" for short.
If we construct wallpapers with each of the sixteen 2x2 checkerboards, we WON'T get sixteen different wallpapers. For instance, checkerboards #2 and #3 generate identical wallpapers. A casebycase inspection shows that the sixteen 2x2 checkerboards generate exactly 7 wallpapers:
wallpaper pattern 1 generated by checkerboard #1 wallpaper pattern 2 generated by checkerboards #2, #3, #5, #9 wallpaper pattern 3 generated by checkerboards #4, #13 wallpaper pattern 4 generated by checkerboards #6, #11 wallpaper pattern 5 generated by checkerboards #7, #9 wallpaper pattern 6 generated by checkerboards #8, #12, #14, #15 wallpaper pattern 7 generated by checkerboard #16
This completes the analysis of the n=2 case.
In the n=3 case there are 2^(3^2) = 512 possible 3x3 checkerboards. Again, a casebycase analysis shows that these generate exactly 64 distinct wallpaper patterns.
In general, let a(n) be the number of distinct wallpaper patterns generated by all possible nxn checkerboards. What I have written above says that a(2) = 7, a(3) = 64. I have computed the values of a(n) for n=1,2,3,4,5:
a(1) = 2 a(2) = 7 a(3) = 64 a(4) = 4156 a(5) = 1342208 a(6) = unknown
The values of a(n) for n > 5 are unknown.
Question: Is there a formula for a(n)? Answer: Probably not but I can't be sure.
Question: Is there a _practical_ algorithm to compute a(n)? Answer: I don't know.
I computed the values of a(n) tabulated above using a computer program that inspects all possibilities. The number of possibilities grows exponentially in n. Computing a(6) is out of the program's reach both in terms of memory requirements and time limits.
It is possible to show that a(n) >= (2^(n^2)) / n^2. I don't know much else about it. If you can provide additional insight, I would like to hear from you.
 Rouben Rostamian

