Given two sorts of squares, (axa) and (bxb), what rectangles can be tiled?

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

[ Editor: the case a=2, b=3, from a March 1998 rec.puzzles thread
"Cutting into squares". ]

Maxim V. Razin (max@razin.zssm.zp.ua) wrote:
: Is it possible to cut a square 1001*1001 into squares 2*2 and 3*3?

: Describe all rectangles which can be cut into such squares.

I say no for this square, and no for all non-obvious cases (the obvious
cases are squares which have a multiple of 2 or a multiple of three for
their side).

Here is my 'proof' (well, argument anyway):

Consider a square with an odd length (we can ignore squares of even
side, since we know they can be tiled).  Each column must have an odd
number of 3x3 squares somewhere along it, leaving an even number of
small squares to be filled by 2x2 squares.

Start from the first column.  There must be an odd number of 3x3
squares that begin there and run to the third column (in particular,
more than zero).  If the large square does not end in the third column,
then we have an odd number of 3x3 squares terminating in the third
column.  Since we already had an odd number of 3x3 squares in the third
column, we must have an odd number of new 3x3 squares starting in the
fourth column, and carrying over to the sixth column.  And so on.  If
the large square does not end after 3n columns, we need new 3x3 squares
in the 3n+1 column, carrying over to the 3n+3 column.  So the side of
an odd square that can be tiled must be divisible by three.

Nice problem.

-- Jonathan Dushoff <dushoff@gate.sinica.edu.tw>