The Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » Math Topics » geometry.puzzles

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 ]
Avni Pllana

Posts: 546
Registered: 12/6/04
Re: Tiling the plane with checkerboard patterns
Posted: Jul 10, 2010 10:32 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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

the term ? quo(b,N) + rem(b,N) ? gives enough insight into the nature of the problem. It is exactly the number of equivalence classes of nxn binary matrices that correspond to binomial(N,i) combinations with respect to horizontal and vertical shifts. Since there are (n horizontal shifts)x(n vertical shifts), the binomial(N,i) should be divided by N.

I wrote a Matlab program implementing the above ideas and according to the numerical results for n=1,2,3, I was able to derive the general formula that fits perfectly to your numerical results for a(n), n=1,?,5. The general formula is to nice not to be true, and a formal proof of it ?is left to the reader?.

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]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.