Geometry problem

[borisp]

Let R be a rectangle in the plane. Suppose that R can be tiled by finitely many rectangles {R_i}, and that each of the R_i has at least one side length that is an integer.

Show that R must have at least one side length that is an integer.

(This is a famous olympiad problem, so I apologize for those that have seen it before and are consequently offended.)

[almostbusto]

the integers are closed under the operation of addition. and thats it right?


i guess to be more thorough:

since the length of the sides of R is the summation of the respective sides of R_i, and since one such side of R_i is an integer... this combined with the first sentence proves that the length of at least one side of R is integer length.


did i not understand the problem? R_i are uniform in size and orientation right? EDIT: upon rereading, i suppose they are not. it still seems "obviously" true. but i'll have to think a bit about it.

[borisp]

The sides of the R_i that are integers can either be horizontal or vertical, and you don't know ahead of time how they are organized. So a side of R is not necessarily the sum of integers, which is essentially why the problem is nontrivial.

[almostbusto]

i think it just came to me.

if you start in the upper left corner. there is an integer path (where each side of R_i tranversed has integer length) that traverses the edges of R_i to either: the bottom edge of R, the right edge of R, or both.

demonstrating that this is true is pretty trivial. start in the upper left corner, one of the two sides that can be traversed must be integer length, traverse that one. then you come to the next intersection. there are two edges that can be traveled (a vertical one and a horizontal one), one of the two must be integer length because each R_i must have a pair of sides that have integer length.

consider the implications of the above fact. they are that the length of one side of R can be computed by summing a series of integers. integers are closed under addition, therefore R has an integer length side.

[borisp]

Looks like that is right, and indeed it is much slicker than the solution(s) that I know. Well done.

[almostbusto]

and illustration that helps demonstrate my proof. hopefully i am right about this.

[borisp]

This is twice now that I've posted problems with the expectation to stump the forum...only to be "disappointed" with a clever answer in under twenty minutes [img]/images/graemlins/smile.gif[/img]

busto, I challenge you to solve the other one...suppose that each cell in an nxn grid of cells is marked either "infected" or "healthy," and that a healthy cell becomes infected if it shares at least two edges with infected cells. Further assume that the process of infection continues until it stabilizes.

Show that for the entire grid to be infected at the end, it must have been true that at least n cells were infected to begin with.