==> geometry/tiling/rectangles.with.squares.s <== A rectangle can be tiled with (axa) and (bxb) squares, iff (i) gcd(a,b)=1 , and any of the following hold: either: both sides of the rectangle are multiples of a; or: both sides of the rectangle are multiples of b; or: one side is a multiple of (ab), and the other is any length EXCEPT one of a finite number of "bad" lengths: those numbers which are NOT positive integer combinations of a & b. { By Sylvester's theorem there are (a-1)(b-1)/2 of these, the largest being (a-1)(b-1)-1. } (ii) gcd(a,b) = d . Then merely apply (i) to the problem with a,b replaced by a/d, b/d and the rectangle lengths also divided by d. i.e. all cells must appear in (dxd) subsquares. ------ PROOF It is clear that (ii) follows from (i), and that simple constructions give the "if" part of (i). For the "only if" part, we prove that... (S) If one side of the rectangle is not divisible by a, and the other is not divisible by b, then the tiling is impossible. The results in (i) follow immediately from (S). To prove (S): ( Chakraborty-Hoey style ). ~~~~~~~~~~~~~~~~ Let the width of the rectangle be a NON-(a-multiple). Then the number of bxb squares starting (i.e. top edge) at row 1 must be a NON-a-multiple. Thus the number of bxb starting at row 2 must BE an a-multiple. Similarly for the number starting at rows 3,4,...,b . Then the number starting at row (b+1) must be a NON-a-multiple again. Similarly the number starting at rows (2b+1), (3b+1), (4b+1),... must all be non-a-multiples. So if the number of rows is NOT a multiple of b, (call it bx+r), then row (bx+1) must have a NON-a-multiple of bxb squares starting there, i.e. at least one, and there is no room left to squeeze it in. [QED] ---- A Rickard-style proof of (S) is ..BBB....BBWWW...WBBB....BBWWW...W(..etc) ~~~~~~~ also possible, by ..BBB....BBWWW...WBBB....BBWWW...W coloring the rectangle in ..BBB....BBWWW...WBBB....BBWWW...W vertical strips as shown here: <- a ->< b-a ><- a ->< b-a > Every square tile covers an a-multiple of black squares. But if the width is a NON-b-multiple, and the number of rows is a NON-a-multiple, then there are a NON-a-multiple of black squares in total. [QED] (Note: the coloring must have 1 column of blacks on the right, and any ==== spare columns of whites on the left.) =================== Bill Taylor. wft@math.canterbury.ac.nz >A Rickard-style proof of (S) is ..BBB....BBWWW...WBBB....BBWWW...W(..etc) > ~~~~~~~ also possible, by ..BBB....BBWWW...WBBB....BBWWW...W >coloring the rectangle in ..BBB....BBWWW...WBBB....BBWWW...W >vertical strips as shown here: <- a ->< b-a ><- a ->< b-a > > >Every square tile covers an a-multiple of black squares. But if the width >is a NON-b-multiple, and the number of rows is a NON-a-multiple, then there >are a NON-a-multiple of black squares in total. [QED] > >(Note: the coloring must have 1 column of blacks on the right, and any > ==== spare columns of whites on the left.) This statement of how to position the colouring isn't good enough, I'm afraid. Take a=4, b=7 and consider e.g. a 19x10 rectangle. Coloured your way, you get: BWWWBBBBWWWBBBBWWWB BWWWBBBBWWWBBBBWWWB ::::::::::::::::::: BWWWBBBBWWWBBBBWWWB BWWWBBBBWWWBBBBWWWB The result has 10*10=100 black squares in it, which *is* a multiple of a=4, despite the fact that 19 is not a multiple of 7 and 10 is not a multiple of 4. Of course, there is an alternative offset for the pattern that does give you the result you want: WWBBBBWWWBBBBWWWBBB WWBBBBWWWBBBBWWWBBB ::::::::::::::::::: WWBBBBWWWBBBBWWWBBB WWBBBBWWWBBBBWWWBBB To show this happens in general: because the width of the rectangle is a non-multiple of b, it is possible to position it on the pattern so that the leftmost column in the rectangle is white and the column just right of the right edge of the rectangle is black. Suppose N columns are black with this positioning. Then the rectangle contains N*H black cells, where H is the height of the rectangle. If we then shift the rectangle right by one, the number of black columns increases by 1 and it contains (N+1)*H black cells. The difference between these two numbers of black cells is H, which is not a multiple of a. Therefore N*H and (N+1)*H cannot both be multiples of a, and so one of these two positionings of the pattern will suit your purposes. David Seal dseal@armltd.co.uk