IBM Research | Ponder This | June 2004 challenges

# Ponder This

## June 2004

<<May June July>>

Ponder This Challenge:

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