Stop 灌水, go participate the IBM June 2004 Challenge :)June 2004 Challenge


--------------------------------------------------------------------------------

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




http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/June2004.html


[kelvin (6-3 9:30, Long long ago)] [ 传统版 | sForum ][登录后回复]1楼

是的，我不该灌了我要走了，去到很远很远的地方，那里才是我的家，我找到快乐的。[烟花 (6-3 14:25, Long long ago)] [ 传统版 | sForum ][登录后回复]2楼