wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Rectangles with one integer dimension
        
(Message started by: Grimbal on Jun 21^st, 2004, 1:47pm)

Title: Rectangles with one integer dimension
Post by Grimbal on Jun 21^st, 2004, 1:47pm

Here is a problem I saw on a forum, but without a solution. For time being, I have been unable to prove or disprove it.

Suppose you have a rectangle that is subdivided into a finite number of smaller rectangles of various sizes, completely filling the rectangle and with no overlap. Suppose that each of the small rectangles has the property that one of its dimension is an integer. Prove that the outer rectangle also has this property.

Title: Re: Rectangles with one integer dimension
Post by TenaliRaman on Jun 21^st, 2004, 3:33pm

::[hide]
if i have not mistaken the question,
i assume that if a rectangle has 1 integer dimension that means there is a pair of opposite sides with integer length.

in which case,
i think the proof is easy.

we know that,
p->q is equivalent to ~q->~p
p : all smaller rectangles have integer dimensions
q : bigger rectangle has integer dimension

we will show ~q->~p
i.e if the bigger rectangle has no integer dimensions then all the smaller rectangles cannot have integer dimension.

Assume we have a large rectangle with no integer dimension.
Now since we have to divide it into rectangles, we can either have a horizontal cut or vertical cut.

Can i divide this rectangle into two rectangles having one integer dimension? No, one of them will have no integer dimensions.

Following this argument recursively, we see that there will be atleast one rectangle which does not have integer dimension.
[/hide]::

Title: Re: Rectangles with one integer dimension
Post by towr on Jun 22^nd, 2004, 12:54am

But aren't you assuming each cut goes through a whole (sub)rectangle?
You could never get something like
[][][]
[][][]
[][][]

So it doesn't apply to all possible divisions of a rectangle, only ones were you make whole cuts recursively

Title: Re: Rectangles with one integer dimension
Post by Barukh on Jun 23^rd, 2004, 1:25am

This statement is indeed true. Here’s a sketch of increadibly simple proof due to Solomon Golomb, the inventor of polyominos.

[smiley=blacksquare.gif][hide]
The proof is by contradiction. Assume that both dimensions of the outer rectangle are not integers.

Imagine an infinite chess-board drawn on the plane, with the side length equal to 1/2. Put the outer rectangle on the plane so that its left and bottom sides are lined up with the lines of the chess-board. Now there are two crusial facts (Try to prove them):

1. Because of the assumption made, the outer rectangle will cover non-equal area of black and white color.
2. Because every small rectangle has at least one integral side, it will cover the same area of black and white color.

That’s the contradiction.
[/hide][smiley=blacksquare.gif]

IMHO, extremely elegant!

Title: Re: Rectangles with one integer dimension
Post by Grimbal on Jun 23^rd, 2004, 11:53am

Wow! Elegant indeed.

Title: Re: Rectangles with one integer dimension
Post by TenaliRaman on Jun 25^th, 2004, 10:49am

Yes you are right towr! I almost convinced myself that any form of cuts can be simulated with a recursive sequence of cuts.Ofcourse ur simple example counters everything i had in mind!

Barukh,
that is really cool!
I am trying to prove the two facts.Unfortunately, these "facts" are not very intuitive (IMHO). Which basically means i have no clue as to how to start proving them. Anyways will try and see if i can get around it. :)

Title: Re: Rectangles with one integer dimension
Post by TenaliRaman on Jul 2^nd, 2004, 2:27pm

Not able to convince myself of the two facts yet. Any help is greatly appreciated!!

Title: Re: Rectangles with one integer dimension
Post by Barukh on Jul 3^rd, 2004, 4:29am

on 07/02/04 at 14:27:51, TenaliRaman wrote:

Not able to convince myself of the two facts yet. Any help is greatly appreciated!!

Here's a hint for fact #2: [hide]What happens if the small rectangle is moved in the direction perpendicular to its integral side[/hide]?

Hope this helps...

Title: Re: Rectangles with one integer dimension
Post by TenaliRaman on Jul 8^th, 2004, 9:19am

:-[
i need a new brain
i am not seeing anything yet! :'(

Title: Re: Rectangles with one integer dimension
Post by towr on Jul 8^th, 2004, 10:14am

You could try drawing it..

Also, integer length line pieces parallel to any of the sides must be collored equally much black as white, so the same goes for a rectangle with an integer side (just cut it up into lines)

Title: Re: Rectangles with one integer dimension
Post by Barukh on Jul 9^th, 2004, 12:14am

TenaliRaman, look at the attached drawing. The blue is the originial position of the rectangle, the red is where it was moved to coincide with the chessboard lines at its integer side.

Title: Re: Rectangles with one integer dimension
Post by TenaliRaman on Jul 10^th, 2004, 10:41am

duh! its so embarassingly obvious!!! :-[
Thanks towr and Barukh! :)

Its ofcourse trivial now as to why Mr Solomon chose the sides to be 1/2, it offers such a simple proof for the first fact!!!

(Simply Brilliant i would say brilliant!!)

Title: Re: Rectangles with one integer dimension
Post by Barukh on Jul 13^th, 2004, 9:20am

You may want to look at the following paper (http://www.cs.toronto.edu/~mackay/rectangles.pdf) for more proofs, generalizations and references.

The complex integration method is amazing! ;D