IBM Research | Ponder This | June 2004 challenges
Skip to main content

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

If you have any problems you think we might enjoy, please send them in. All replies should be sent to:


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