From: Douglas Zare <zare@math.columbia.edu>
Subject: Re: Rectangles Divided Into Squares
Date: Thu, 16 Sep 1999 17:48:42 -0400
Newsgroups: sci.math
Keywords: ratio of sides rational

Clive Tooth wrote:

> Leroy Quet wrote in message ...
>
> >This one should be easy. Let R be a  x by y rectangle. Show that R can
> >be subdivided completely into squares if, and only if, x/y is
> >rational.
>
> This is problem 23 at Douglas Zare's problem page:
> http://www.its.caltech.edu/~zare/prob_all.html

That link will still work for a couple of weeks, but it will move to
http://www.math.columbia.edu/~zare/prob_all.html shortly.

Elsewhere, someone asked for another elegant solution to this problem besides
the electric resistance. I'm rather partial to considering the exterior
square of R as a Q-vectorspace, but if that fails to be sufficiently elegant
for you consider the following:

Turn a tiled rectangle on its corner and project, sending all vertices to the
sum of the coordinates. One may as well rescale so that the extreme points,
vertices of the rectangle, are sent to 0 and 1. Each interior vertex must be
the top or bottom vertex of a square, so its value is the average of two
other values. This is a finite set such that all elements are averages of two
others except possibly 0 or 1, so this fits the hypotheses of another problem
on my list, to show that the elements of any such set must be rational. In
particular, the value corresponding to the top or bottom vertex of the
rectangle must be rational.

I know of a few proofs that the numbers must be rational. Again, I like
thinking of R as a Q-vectorspace (and using a Hamel basis), but one can also
solve this problem by using ordinary rational linear algebra. One assembles
the equations which show that the numbers are averages of each other and
substitutes carefully to get rational conditions: each number can be
expressed as a positive rational linear combination of greater numbers. This
may be the proof another poster on this thread was trying to find. I believe
there should be a proof using the obvious martingale on the numbers, but I
don't see one.

I encountered both of these problems, and the above connection between the
two, in the Budapest Semesters in Mathematics program.

Douglas Zare