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 ]
 Rouben Rostamian Posts: 193 Registered: 12/6/04
Re: Tiling the plane with checkerboard patterns
Posted: Jul 14, 2010 6:45 PM

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.

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