Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » Math Topics » geometry.puzzles.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Rouben Rostamian

Posts: 193
Registered: 12/6/04
Tiling the plane with checkerboard patterns
Posted: Jul 6, 2010 4:06 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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)?
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



Date Subject Author
7/6/10
Read Tiling the plane with checkerboard patterns
Rouben Rostamian
7/7/10
Read Re: Tiling the plane with checkerboard patterns
Avni Pllana
7/8/10
Read Re: Tiling the plane with checkerboard patterns
mark
7/9/10
Read Re: Tiling the plane with checkerboard patterns
Rouben Rostamian
7/9/10
Read Re: Tiling the plane with checkerboard patterns
Avni Pllana
7/9/10
Read Re: Tiling the plane with checkerboard patterns
Rouben Rostamian
7/10/10
Read Re: Tiling the plane with checkerboard patterns
Avni Pllana
7/10/10
Read Re: Tiling the plane with checkerboard patterns
mark
7/11/10
Read Re: Tiling the plane with checkerboard patterns
Rouben Rostamian
7/11/10
Read Re: Tiling the plane with checkerboard patterns
mark
7/11/10
Read Re: Tiling the plane with checkerboard patterns
Rouben Rostamian
7/11/10
Read Re: Tiling the plane with checkerboard patterns
mark
7/12/10
Read Re: Tiling the plane with checkerboard patterns
Rouben Rostamian
7/13/10
Read Re: Tiling the plane with checkerboard patterns
mark
7/14/10
Read Re: Tiling the plane with checkerboard patterns
Rouben Rostamian
7/14/10
Read Re: Tiling the plane with checkerboard patterns
mark
7/11/10
Read Re: Tiling the plane with checkerboard patterns
Rouben Rostamian
7/14/10
Read Re: Tiling the plane with checkerboard patterns
Avni Pllana
7/14/10
Read Re: Tiling the plane with checkerboard patterns
Rouben Rostamian
7/13/10
Read Re: Tiling the plane with checkerboard patterns
Mary Krimmel
7/14/10
Read Re: Tiling the plane with checkerboard patterns
Rouben Rostamian
7/14/10
Read Re: Tiling the plane with checkerboard patterns
mark

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.