Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

tiling a rectangular grid

3 views
Skip to first unread message

quasi

unread,
Jan 20, 2011, 2:41:18 AM1/20/11
to
Do there exist positive integers m,n and relatively prime positive
integers a,b, neither of which is a factor of either m or n, such that
an m x n grid can be tiled with some combination of a x a and b x b
tiles?

quasi

quasi

unread,
Jan 20, 2011, 3:02:10 AM1/20/11
to

Ok, the proof just hit me -- it's easy -- the answer is "no".

But my proof doesn't appear to generalize to the case of 3
types of tiles, so here's the revised question ...

Do there exist positive integers m,n and relatively prime

positive integers a,b,c, none of which is a factor of either

m or n, such that an m x n grid can be tiled with some

combination of a x a, b x b, c x c tiles?

quasi

quasi

unread,
Jan 20, 2011, 3:09:21 AM1/20/11
to
On Thu, 20 Jan 2011 03:02:10 -0500, quasi <qu...@null.set> wrote:

>On Thu, 20 Jan 2011 02:41:18 -0500, quasi <qu...@null.set> wrote:
>
>>Do there exist positive integers m,n and relatively prime
>>positive integers a,b, neither of which is a factor of
>>either m or n, such that an m x n grid can be tiled with
>>some combination of a x a and b x b tiles?
>
>Ok, the proof just hit me -- it's easy -- the answer is "no".

I take it back -- my "easy proof" just disintegrated.

>But my proof doesn't appear to generalize to the case of 3
>types of tiles, so here's the revised question ...
>
>Do there exist positive integers m,n and relatively prime
>positive integers a,b,c, none of which is a factor of either
>m or n, such that an m x n grid can be tiled with some
>combination of a x a, b x b, c x c tiles?

Ok, so both problems are in play.

quasi

achille

unread,
Jan 20, 2011, 3:29:08 AM1/20/11
to

The case of 3 types of tiles is trivial.
a 7x13 rectangle can be tiled by 8*2x2, 1*3x3 and 2*5x5 squares.

Gerry Myerson

unread,
Jan 20, 2011, 5:34:09 PM1/20/11
to
In article <8enfj6hbh9ueutceq...@4ax.com>,
quasi <qu...@null.set> wrote:

You may be interested in Theorem 5 of
http://www.combinatorics.org/Volume_11/PDF/v11i1n7.pdf

The rest of the paper may interest you, as well.

--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)

quasi

unread,
Jan 21, 2011, 12:52:23 AM1/21/11
to
On Fri, 21 Jan 2011 09:34:09 +1100, Gerry Myerson
<ge...@maths.mq.edi.ai.i2u4email> wrote:

>In article <8enfj6hbh9ueutceq...@4ax.com>,
> quasi <qu...@null.set> wrote:
>
>> Do there exist positive integers m,n and relatively prime
>> positive integers a,b, neither of which is a factor of either
>> m or n, such that an m x n grid can be tiled with some
>> combination of a x a and b x b tiles?
>
>You may be interested in Theorem 5 of
>http://www.combinatorics.org/Volume_11/PDF/v11i1n7.pdf
>
>The rest of the paper may interest you, as well.

Those results pretty much clinch the answer to my question, and more.

Thanks.

quasi

0 new messages