Search All of the Math Forum:

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

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

 Messages: [ Previous | Next ]
 Rouben Rostamian Posts: 193 Registered: 12/6/04
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 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
I would like to hear from you.

--
Rouben Rostamian

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