Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Tiling the plane with checkerboard patterns
Replies: 21   Last Post: Jul 14, 2010 10:33 PM

 Messages: [ Previous | Next ]
 mark Posts: 206 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 side-by-side
> horizontally
> and vertically. Thus the entire two-dimensional
> 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 case-by-case 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 case-by-case 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)?
>
> 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
> 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.

Date Subject Author
7/6/10 Rouben Rostamian
7/7/10 Avni Pllana
7/8/10 mark
7/9/10 Rouben Rostamian
7/9/10 Avni Pllana
7/9/10 Rouben Rostamian
7/10/10 Avni Pllana
7/10/10 mark
7/11/10 Rouben Rostamian
7/11/10 mark
7/11/10 Rouben Rostamian
7/11/10 mark
7/12/10 Rouben Rostamian
7/13/10 mark
7/14/10 Rouben Rostamian
7/14/10 mark
7/11/10 Rouben Rostamian
7/14/10 Avni Pllana
7/14/10 Rouben Rostamian
7/13/10 Mary Krimmel
7/14/10 Rouben Rostamian
7/14/10 mark