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