Partitioning a Rectangle...

[Anza Power]

I've been pondering this for a few months now and haven't got a clue yet what to do...

Prove that if you have a rectangle and you partition it into smaller rectangles such that every rectangle has at least 1 edge of integer length, then the large rectangle has 1 edge of integer length.

The proof is supposed to be simple by using the fact that in a graph the number of nodes with odd degrees is even, and it's generalized for Rⁿ, but I'm still stuck even on R²...

Edited June 11, 2012 by Anza Power

[Rox53]

If you start with a rectangle with no integer edges, then at least one of the smaller rectangles will also lack integer edges. This is heuristically true - but I can't prove it yet.

If my first statement can be proved, then it follows that the original proposition (If you have a rectangle and you partition it into smaller rectangles such that every rectangle has at least 1 edge of integer length, then the large rectangle has 1 edge of integer length) must be true.

[curr3nt2]

Start with a rectangle with at least two integer edges. (Just nitpicking since a rectangle can't have only one integer edge)

To create a larger rectangle by adding another rectangle with at least two integer edges there are two options.

Make them adjacent along the non integer edge which would add the two integer edge lengths to make the new rectangle's integer edge.

Make them adjacent along the integer edge which would make the new rectangle have an edge length equal to the integer edge of the two smaller rectangles.

Repeat. There's just no way to add the second rectangle without retaining at least two integer edges.

Any rectangle you add, if partitioning is possible, would be created the same way from the smallest rectangle.

[witzar]

Look here for proofs (there are many):

http://mathdl.maa.org/images/upload_library/22/Ford/Wagon601-617.pdf