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]

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

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 /images/graemlins/smile.gif

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.

[almostbusto]

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?

[borisp]

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

[borisp]

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.

[almostbusto]

you are right borisp. i guess if you can prove that there exists a path from one end of R to the other, then my proof holds. i am not sure there necessarily is such a path however.

I suspected it might have problems. mostly because i rarely figure out proofs where you have to be clever on my first try.

[blah_blah]

I have seen this problem before (it certainly is well known enough to be considered part of mathematical folklore).

One of the nicer ways is to integrate exp(2 \pi i (x+y)) over R (which is of course the same as integrating exp(2\pi i (x+y)) over the union of all of the rectangles ...)

there is another solution involving checkerboards but I am an analyst by heart and by training and so I stick to my most familiar tools /images/graemlins/smile.gif

[borisp]

[ QUOTE ]
I have seen this problem before (it certainly is well known enough to be considered part of mathematical folklore).

One of the nicer ways is to integrate exp(2 \pi i (x+y)) over R (which is of course the same as integrating exp(2\pi i (x+y)) over the union of all of the rectangles ...)

there is another solution involving checkerboards but I am an analyst by heart and by training and so I stick to my most familiar tools /images/graemlins/smile.gif

[/ QUOTE ]
Shut up!!...no offense /images/graemlins/tongue.gif

[blah_blah]

since the majority of 'recreational' mathematicians are not capable of integrating a complex function over a curve in R^2, I think that I haven't spoiled your problem /images/graemlins/smile.gif

[almostbusto]

[ QUOTE ]
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.

[/ QUOTE ] wait a minute, yes you are guaranteed to land at the corner point with at least one other R_i, but i am not sure i can prove that the path necessarily hits the other side.


can you visualize a corner of an R_i that doesn't share that corner with another R_i? maybe you could demonstrate with a pic because i can't see it right now.

[pzhon]

[ QUOTE ]
[ QUOTE ]
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.

[/ QUOTE ] wait a minute, yes you are guaranteed to land at the corner point with at least one other R_i, but i am not sure i can prove that the path necessarily hits the other side.


[/ QUOTE ]
This is part of one of the relatively well-known proofs for this problem, which was discussed in Stan Wagon's award-winning paper, "Fourteen Proofs Of a Result About Tiling a Rectangle" (http://links.jstor.org/sici?sici=0002-9890(198708%2F09)94%3A7<601%3AFPOARA>2.0.CO%3B2-Y) American Mathematical Monthly, Aug/Sep 1987. There is something left to prove. In the spirit of this thread, though, I won't post the rest of the proof in the next few days.

[Freyalise]

Bah I've seen the checkerboard solution now and spoiled it.
Very nice problem though which I had not seen before.

[thylacine]

[ QUOTE ]
I have seen this problem before (it certainly is well known enough to be considered part of mathematical folklore).

One of the nicer ways is to integrate exp(2 \pi i (x+y)) over R (which is of course the same as integrating exp(2\pi i (x+y)) over the union of all of the rectangles ...)

there is another solution involving checkerboards but I am an analyst by heart and by training and so I stick to my most familiar tools /images/graemlins/smile.gif

[/ QUOTE ]

I thought there was a rule against problems where the easiest solution involves calculus. Right? Does this mean there is an even easier solution than this?

[Freyalise]

[ QUOTE ]
[ QUOTE ]
I have seen this problem before (it certainly is well known enough to be considered part of mathematical folklore).

One of the nicer ways is to integrate exp(2 \pi i (x+y)) over R (which is of course the same as integrating exp(2\pi i (x+y)) over the union of all of the rectangles ...)

there is another solution involving checkerboards but I am an analyst by heart and by training and so I stick to my most familiar tools /images/graemlins/smile.gif

[/ QUOTE ]


I thought there was a rule against problems where the easiest solution involves calculus. Right? Does this mean there is an even easier solution than this?

[/ QUOTE ]

There is an extremely simple solution, one that a child could understand.

I didn't see it myself so of course I won't spoil the problem by posting it.