Geometry problem
 

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.)

Re: Geometry problem
 

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.

Re: Geometry problem
 

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.

Re: Geometry problem
 

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.

Re: Geometry problem
 

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

Re: Geometry problem
 

http://img408.imageshack.us/img408/3599/illusmj3.gif

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

Re: Geometry problem
 

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.

Re: Geometry problem
 

is this the same problem that you already posted?

i could lie and look like a genius, but i must admit i have already peaked into that thread and saw that the fact that the perimeter of the infected cells as a whole doesn't increase over time is basically the key to the proof. at least its something like that, i don't have a great memory.

bonus points for being honest?

Re: Geometry problem
 

Ehh, no, but I subtract points from myself for lack of originality.

Re: Geometry problem
 

Ok, now I subtract points from myself for agreeing to a fake solution. When you choose to traverse along an integer path, you are not necessarily guaranteed to land at a "corner." It is necessary to be at a corner before you are guaranteed to have an integer path along which to travel.

Try again.