IBM Ponder This #074 · 2004 年 6 月

单位正方形 [0,1]×[0,1] 内给定 N 个不同的点，其中包括原点 (0,0)。能否构造 N 个完全位于正方形内、边平行于坐标轴的矩形，使每个给定点分别是一个矩形的左下角，矩形两两不相交，且总面积至少为 1/2？

例如 N=3，给定点为 (0,0)、(0.2,0.4)、(0.8,0.6)，可选矩形 [0,1]×[0,0.39]、[0.2,0.79]×[0.4,1]、[0.8,1]×[0.6,1]。面积分别为 0.39、0.354、0.08，总和 0.824。

允许退化成线段或点的矩形，但不同矩形连一个公共点也不允许。

证明对任何给定点集都能做到，或者给出包含原点的反例点集。原题发表于 2004 年，当时将此问题列为尚未解决。

解答

认真尝试后再打开

待补充。