点染色问题

继上次的硬币游戏解答在此)之后,Sariel又出了一个有意思的题目。

给定平面上若干个点。证明总存在一个黑白染色方法,使得对于平面上任何一个直线,若此直线这一侧有多于50个点,则此侧的点颜色不完全一样。

更多:

  1. 这是一个研究性问题,从一些论文里抽取,会比较难。
  2. 50这个数字没有特殊的含义,改成4和8应该也可以。
  3. 推广这个问题?

写于2008年八月 20日

关于 »
3条留言 -> 跳到留言表格
  • At 2008.08.28 09:25, Du F. said:

    答案呢?

    • At 2009.03.30 16:56, Myth5 said:

      求出点集的凸包,设这些点按凸包的顺序依次为1,2..k,将标号为奇数的点染黑色,标号为偶数的点染白色。对于相邻的三个点x-1,x,x+1,若由它们组成的三角形(不包括线段)内存在别的点,则这些点染与点x不同的颜色。
      可能有一些细节问题,如共线,重点等。
      ps:I am an OIer

      • At 2010.01.10 14:32, gao said:

        Sariel是什么人?

        (Required)
        (Required, not published)

          B | I | U | D | 添加链接 | 插入引用 | 插入代码 | 插入表情 | | + | ?

        guest | 注册 | 管理

        阅微堂

        理工科背景的证券从业人员
        Loading...
        Loading...
        Loading...