IT技术博客大学习 共学习 共进步

IMO2011趣题:总存在一条将会遍历所有点的直线

Matrix67: My Blog 2011-07-30 21:23:15 累计浏览 3,122 次
本机暂存

     下面这个精彩的问题来自于刚刚结束的 IMO 2011 中的第 2 题:

     设 S 是平面上包含至少两个点的一个有限点集,其中没有三点在同一条直线上。所谓一个“风车”是指这样一个过程:从经过 S 中单独一点 P 的一条直线 l 开始,以 P 为旋转中心顺时针旋转,直至首次遇到 S 中的另一点,记为点 Q 。接着这条直线以 Q 为新的旋转中心顺时针旋转,直到再次遇到 S 中的某一点,这样的过程无限持续下去。

         证明:可以适当选取 S 中的一点 P ,以及过 P 的一条直线 l ,使得由此产生的“风车”将 S 中的每一点都无限多次用作旋转中心。

         注意,由于两点确定的直线只有有限多条,因此直线无限旋转下去,必然会出现和以前某个时刻相同的状态,于是产生循环。另外,由于直线旋转的过程是可逆的,我们不必担心最终产生的是一个 ρ 字形的循环。因此,我们实际上只需要证明,存在这样一条初始直线,它可以碰到所有的点。

    原图已失效         原图已失效

     我用 Mathematica 写了一个程序,做了一些直观的动画。如图所示的由 6 个点构成的点集,适当地选择初始直线就能遍历所有的点,但错误的选择将会导致有一些点永远也碰不到。

     IMO 2011 赛后统计资料显示,这道漂亮的问题竟然是六道题中第二难的题(第一难的题是最后一道)。 polymath blog 组织了 mini-polymath3 活动,邀请众人一同讨论这道题的解法。活动开始后的第 74 分钟,有人给出了正确的解法。果然不出所料,神题就该有神解,这道题有一个异常简单巧妙的证明方法。

    原图已失效

建议继续学习

  1. 程序算法与人生选择 (累计阅读 9,120)
  2. 如果用户在5分钟内重复上线,就给他发警告,问如何设计? (累计阅读 5,960)
  3. 经典证明:任意三角形都能被分成n≥4个等腰三角形 (累计阅读 5,880)
  4. 44个精彩的物理趣题 (累计阅读 4,420)
  5. 收割庄稼v.s.砍伐大树――如何解决问题 (累计阅读 3,260)
  6. 趣题:随机折断的木棒 (累计阅读 3,180)
  7. 打印质数的各种算法 (累计阅读 3,141)
  8. 用相同的面组成多面体,凸多面体不一定会更大 (累计阅读 2,840)
  9. 怎样把一个钝角三角形分成若干个锐角三角形 (累计阅读 2,361)
  10. Kolakoski序列:我们知道的还是太少 (累计阅读 2,323)