mark
Posts:
204
Registered:
12/6/04


Re: Tiling the plane with checkerboard patterns
Posted:
Jul 8, 2010 7:37 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 > ,1 0,1 > 0,0 0,1 1,0 1,1 0,0 0,1 1,0 > ,0 1,1 > > 1,0 1,0 1,0 1,0 1,1 1,1 1,1 > ,1 1,1 > 0,0 0,1 1,0 1,1 0,0 0,1 1,0 > ,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 >
Rouben,
I don't know if this is helping or not, but I think your definition of the problem has a flaw. The reason #2,#3,#5, & #9 create the same wallpaper is that "the plane" does not have any corners. On the same note I think "the plane" does not have any rotational orientation. If that is true, #4,#13,#6, & #11 also generate the same wallpaper. This would change all your numbers. a(2) now =6. I think a formula is possible for either definition. I'm working on it. Thanks for the interesting puzzle.

