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
Re: Tiling the plane with checkerboard patterns
Posted: Jul 14, 2010 6:45 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Hello Avni, I am surprised with the discrepancy you have found
in the a(6) case. I still hold hope that your formula does
give the correct values for all a(n). Could it be that the
discrepancy is due to Matlab's floating point arithmetic?

Since you and Mark have both noted the effect of parity of n,
I want to point out that I have reason to believe that what
matters is not whether n is odd or even, but whether it is
prime or composite. I don't have a fool-proof argument to
support that right now; just a preliminary analysis.
I will write about this again if I find out more.

Rouben

---- original message -------------------------------------------
From: Avni Pllana <avniu66@hotmail.com>
Date: Wed, 14 Jul 2010 12:14:51 +0000 (UTC)
To: approve@support1.mathforum.org
To: geometry-puzzles@support1.mathforum.org
Subject: Re: Tiling the plane with checkerboard patterns

> On Fri, Jul 09, 2010 at 06:00:32PM +0000, Avni Pllana
> wrote:

> >
> > 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
> >
> > %%%%%%%%%%%%%%%%%%%%%%%%

>
>
> Avni, that's wonderful! It produces the exact
> values for a(n), n=1,2,3,4,5. Do you have a proof
> for the general case?
>
> Rouben
>
> Aside: Since the Matlab program above is limited
> by its dependence on floating point arithmetic
> to the range n=1,2,...,7, I recoded your algorithm
> in Maple which performs integer arithmetic with no
> limits. Here is the Maple's version of your formula:
>
> a := proc(n::posint)
> local N, b;
> N := n^2;
> b := binomial(N,i);
> return sum( iquo(b,N) + irem(b, N), i=0..N);
> end proc:
>
> Then the command "seq(a(n), n=1..9);" produces
> the values of a(n) for n=1,2,...,9:
>
> n a(n)
> 1 2
> 2 7
> 3 64
> 4 4156
> 5 1342208
> 6 1908874521
> 7 11488774559744
> 8 288230376151712689
> 9 29850020237398251228192
>


Hi Rouben,

I tried to find further numerical evidence about my sum formula. A comparison of the number of equivalence classes using the Matlab program and using the sum formula is shown below:

n=1
N=1^2=1

Mat_1=[1 1]
Sum_1=[1 1]

a(1)=2, Matlab
a(1)=2, sum formula
________________________

n=2
N=2^2=4

Mat_2=[1 1 3 1 1]
Sum_2=[1 1 3 1 1]

a(2)=7, Matlab
a(2)=7, sum formula
________________________

n=3
N=3^2=9

Mat_3=[1 1 4 12 14 14 12 4 1 1]
Sum_3=[1 1 4 12 14 14 12 4 1 1]

a(3)=64, Matlab
a(3)=64, sum formula
________________________

n=4
N=4^2=16

Mat_4=[1 1 9 35 122 273 511 715 822 715 511 273 122 35 9 1 1]
Sum_4=[1 1 15 35 125 273 508 715 810 715 508 273 125 35 15 1 1]

a(4)=4156, Matlab
a(4)=4156, sum formula
________________________

n=5
N=5^2=25

Mat_5=[1 1 12 92 506 2130 x x ...]
Sum_5=[1 1 12 92 506 2130 .......]

a(5)=1342208, Rouben
a(5)=1342208, sum formula
________________________

n=6
N=6^2=36

Mat_6=[1 1 19 201 1649 x x ...]
Sum_6=[1 1 35 210 1645 .......]

a(6)= ?, Matlab
a(6)=1908874521, sum formula
________________________

Above results show that for n odd the sum formula gives exactly the number of equivalence classes and exact a(n).

For n even the sum formula does not give the exact number of equivalence classes, but it gives exact a(n), at least for n=2 and n=4.

These results resemble somehow the behavior of magic squares.

Best regards,
Avni



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.