Which n*n squares cannot be tiled by k*k squares,
where all k are allowed which don't divide n?
Show that this set is finite.
--------------------------------------------------
From: devjoe@wilma.che.utexas.edu (Joseph W. DeVincentis)
Newsgroups: rec.puzzles
Subject: Re: Cutting squares -- CHALLENGE
Date: 23 Mar 1998 17:57:50 GMT
Organization: JWD's computer in CPE
Matthew Daly wrote:
>I'll never forget the time that dushoff@gate.sinica.edu.tw (Jonathan
>Dushoff) said:
>>I say 60x60. If anybody can cut a 60x60 square into smaller squares,
>>without using one whose side divides 60, or provide a larger (finite)
>>square that cannot be so cut, I would like to know about it.
>
>Why did you choose 60? I find it hard to believe that you could so tile
>any square whose length was an antiprime (= a positive natural number
>that has more factors than any number less than it.) For instance, what
>about 120?
I worked on this problem myself and I think I reached the same point
Jonathan did -- with about 20 sizes of squares still untiled, most
probably untileable, but no proof that they can't be tiled, and the
greatest of these is 60.
For the specific case of 120, it can be tiled by making 63-unit wide
borders along two edges, composed of 9x63 and 7x63 blocks constructed
from 7x7 and 9x9 squares. Fill a 63x63 square with either square, and
then use 3 7x63's and 4 9x63's to make a 57x63, and make another 57x63
on the other side, and you have a 57x57 square left. Obviously this
particular tiling does not scale down to a 60x60, but it works for any
larger multiple of 60 that is not divisible by 7 or 9.
For very large squares, you can always just choose the two smallest
allowable relatively prime subsquare sizes to make a tiling of this
sort. I.e., for 1260 (= 2*2*3*3*5*7), the first number divisible by
all the numbers up to 10, you can do it with 11's and 13's, making a
border 143 units wide and leaving a 1117x1117 square filling up the
remaining space.
It's the small squares that cause problems -- typically you can't
complete the border because the two subsquare sizes you chose can't
be combined in a way that adds up to the small square's size (needed
for part of the border). For instance this happens when trying to use
7's and 8's to tile a 60x60 (can't fill 4x56 with 7's and 8's) and when
trying to use 5's and 7's to tile a 48x48 (can't fill 13x35 with 5's and
7's). Sometimes the small square left over may be a factor of the main
square, or the "blocks" simply don't fit in the square at all (such as
when trying to tile a 60x60 with 7's and 9's, in imitation of the 120x120
tiling). When the squares are large enough, the first issue is no longer
a problem, as any sufficiently long length of border can be constructed
from two relatively prime square sizes, and the second issue is also no
longer a problem, as the border width becomes less than half the size
of the main square, making the leftover square more than half, but less
than the whole, or obviously not a factor.
I was not able to find another method of tiling any of the squares that
could not be tiled by this method for *some* suitable subsquare sizes,
in the way I was able to tile the 19x19 with 2x2's, 3x3's, and 5x5's in
another problem (in this one, a 13x13 is allowable in tiling a 19x19 so
we don't have the same problem).
/dev/joe
From: John Rickard
Newsgroups: rec.puzzles
Subject: Re: Cutting squares -- CHALLENGE
Date: 23 Mar 1998 18:24:33 +0000 (GMT) and
Date: 25 Mar 1998 13:51:13 +0000 (GMT)
Organization: Virata Ltd
Joseph W. DeVincentis wrote:
: >>I say 60x60. If anybody can cut a 60x60 square into smaller squares,
: >>without using one whose side divides 60, or provide a larger (finite)
: >>square that cannot be so cut, I would like to know about it.
[...]
: I worked on this problem myself and I think I reached the same point
: Jonathan did -- with about 20 sizes of squares still untiled, most
: probably untileable, but no proof that they can't be tiled, and the
: greatest of these is 60.
Same here. The method you describe works for all sizes except for:
1 to 10, 12, 14, 15, 16, 18, 20, 24, 30, 36, 48, 60.
It's easy to prove that none of 1-10 and 12 can be tiled; I don't have
any proofs either way for any of the others. (Though the smaller
numbers shouldn't be too hard to check.)
Update: 25 Mar
If I haven't made any other mistakes, I can show that none of 1-10,
12, 14, 15, 16, 18, 20, 24, 30 can be tiled. This leaves 36, 48, 60
unsettled.
--
John Rickard