|
|
Re: Tiling the plane with checkerboard patterns
Posted:
Jul 9, 2010 1:59 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)?
> 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
>
Hi Rouben,
I think I found the right algorithm/formula for a(n):
%%%%%%%%%%%%%%%%%%%%%%%%
for n=1:5
N=n^2;
A=2;
for i=1:N-1
A=A+floor(nchoosek(N,i)/N)+mod(nchoosek(N,i),N);
end
a(n)=A;
end
%%%%%%%%%%%%%%%%%%%%%%%%
Best regards,
Avni
|
|
