Ponder This Challenge - June 2004 - Rectangles in the unit square

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

Solution

• Click here to view the solution

  ANSWER:

  If our N points are equally spaced along the main diagonal: (i/N, i/N) for i=0,1,...,N-1, then any solution will have area at most (N(N+1)/2)/(N*N) = (N+1)/(2*N), which is slightly larger than 1/2. But a general solution is not known.

Solvers