From: Douglas Zare 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