• 0

Partitioning a Rectangle...

Question

Posted (edited) · Report post

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 Rn, but I'm still stuck even on R2...

Edited by Anza Power
0

Share this post


Link to post
Share on other sites

3 answers to this question

  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.