矩形分割问题

问题描述:在一个矩形内部有\(n\)个不重合的点,其中任意两个点的连线均不与矩形的边平行。现在将矩形分割成若干个小矩形,使得所有小矩形的边均与原矩形的边平行,且已知点不在任意一个小矩形的内部,试证明满足上述条件时分割得到的小矩形个数不少于\(n+1\)个。

这道题是某年IMO的预选题,这个结论应该是非常直观的,但要把原因给说清楚却不太容易。根据题目中少得可怜的数量关系建立起不等式,最后得出结论,我觉得有趣之处就在这里。

Solution

假设在一种方案中矩形被分为了\(k\)个小矩形,我们将该方案里所有的矩形的顶点分为以下三类:

  • 原矩形的顶点
  • 恰为两个小矩形公共顶点的点(T型交点),假设这类点总共有\(a\)个
  • 恰为四个小矩形公共顶点的点(十字型交点),假设这类点总共有\(b\)个

容易发现每个顶点必然属于上面一类,并且我们知道\(k\)个小矩形共有\(4k\)个顶点,所以\(4k=4+2a+4b\)。

根据题意,现在已知点都在小矩形的边上,沿着每个已知点所在的小矩形的边向外延伸,最终都会碰到T型交点。由于任意两个已知点的连线不与矩形的边平行,所以按上述方法总共能碰到\(2n\)个不同的T型交点,则有\(a\geq 2n\)。

将不等式代入到上面的等式中得\(4k\geq 4+4n+4b\geq 4+4n\),两边除掉系数后得\(k\geq n+1\),即分割得到的小矩形个数不少于\(n+1\)个。

发表评论

电子邮件地址不会被公开。 必填项已用*标注