wu :: forums
« wu :: forums - Rectangles with one integer dimension »

Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 8:44am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Icarus, SMQ, Eigenray, Grimbal, william wu, towr)
   Rectangles with one integer dimension
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Rectangles with one integer dimension  (Read 2255 times)
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Rectangles with one integer dimension  
« on: Jun 21st, 2004, 1:47pm »
Quote Quote Modify Modify

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.
IP Logged
TenaliRaman
Uberpuzzler
*****



I am no special. I am only passionately curious.

   


Gender: male
Posts: 1001
Re: Rectangles with one integer dimension  
« Reply #1 on: Jun 21st, 2004, 3:33pm »
Quote Quote Modify Modify

::
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.
::
IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Rectangles with one integer dimension  
« Reply #2 on: Jun 22nd, 2004, 12:54am »
Quote Quote Modify Modify

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
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Rectangles with one integer dimension  
« Reply #3 on: Jun 23rd, 2004, 1:25am »
Quote Quote Modify Modify

This statement is indeed true. Here’s a sketch of increadibly simple proof due to Solomon Golomb, the inventor of polyominos.
 
[smiley=blacksquare.gif]
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.
[smiley=blacksquare.gif]
 
IMHO, extremely elegant!
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: Rectangles with one integer dimension  
« Reply #4 on: Jun 23rd, 2004, 11:53am »
Quote Quote Modify Modify

Wow!  Elegant indeed.
IP Logged
TenaliRaman
Uberpuzzler
*****



I am no special. I am only passionately curious.

   


Gender: male
Posts: 1001
Re: Rectangles with one integer dimension  
« Reply #5 on: Jun 25th, 2004, 10:49am »
Quote Quote Modify Modify

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.  Smiley
IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
TenaliRaman
Uberpuzzler
*****



I am no special. I am only passionately curious.

   


Gender: male
Posts: 1001
Re: Rectangles with one integer dimension  
« Reply #6 on: Jul 2nd, 2004, 2:27pm »
Quote Quote Modify Modify

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

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Rectangles with one integer dimension  
« Reply #7 on: Jul 3rd, 2004, 4:29am »
Quote Quote Modify Modify

on Jul 2nd, 2004, 2:27pm, TenaliRaman wrote:
Not able to convince myself of the two facts yet. Any help is greatly appreciated!!

Here's a hint for fact #2: What happens if the small rectangle is moved in the direction perpendicular to its integral side?
 
Hope this helps...
IP Logged
TenaliRaman
Uberpuzzler
*****



I am no special. I am only passionately curious.

   


Gender: male
Posts: 1001
Re: Rectangles with one integer dimension  
« Reply #8 on: Jul 8th, 2004, 9:19am »
Quote Quote Modify Modify

Embarassed
i need a new brain
i am not seeing anything yet!   Cry
IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Rectangles with one integer dimension  
« Reply #9 on: Jul 8th, 2004, 10:14am »
Quote Quote Modify Modify

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)
« Last Edit: Jul 8th, 2004, 10:43am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Rectangles with one integer dimension   Rectangles.JPG
« Reply #10 on: Jul 9th, 2004, 12:14am »
Quote Quote Modify Modify

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.
IP Logged

TenaliRaman
Uberpuzzler
*****



I am no special. I am only passionately curious.

   


Gender: male
Posts: 1001
Re: Rectangles with one integer dimension  
« Reply #11 on: Jul 10th, 2004, 10:41am »
Quote Quote Modify Modify

duh! its so embarassingly obvious!!!  Embarassed
Thanks towr and Barukh!  Smiley
 
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!!)
IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Rectangles with one integer dimension  
« Reply #12 on: Jul 13th, 2004, 9:20am »
Quote Quote Modify Modify

You may want to look at the following paper for more proofs, generalizations and references.
 
The complex integration method is amazing!  Grin
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board