June 2004
Puzzle for June 2004.
"We heard this puzzle from a friend, but its origins are unclear. Pointers to its attribution would be appreciated."
Given N distinct points in the unit square [0,1]x[0,1], including the origin (0,0) as one of the N points. Can you construct N rectangles, contained in the unit square, with sides parallel to the coordinate axes, pairwise non-intersecting, such that each of our N given points is the lower-left-hand corner of one of the rectangles, and such that the total area of the rectangles is at least 1/2?
For example, N=3 and the points are (0,0), (0.2,0.4) and (0.8,0.6). The three rectangles could be [0,1]x[0,0.39], [0.2,0.79]x[0.4,1], and [0.8,1]x[0.6,1]. Their areas are 0.39, 0.354 and 0.08, summing to 0.824, which is larger than 1/2.
(We allow degenerate rectangles -- a point or a line segment -- but still do not allow them to intersect with other rectangles, even in a single point.)
Your challenge: either prove that such a construction is always possible, or give a set of N distinct points (including the origin) for which it is impossible. The first ten correct solvers will be listed on the website.
Caveat: To the best of our knowledge, the problem is unsolved.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
06/01/2004 @ 9:00 AM ET
Solution:
07/01/2004 @ 8:30 AM ET
List Updated:
06/01/2004 @ 9:00 AM ET
People who answered correctly:
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.