Puzzleup 2010 比赛快开始了，大家用SQL解答啊

lastwinner

那为什么要加减相隔呢？

nlrte13

原帖由 lastwinner 于 2010-10-29 14:00 发表
那为什么要加减相隔呢？

加重复的要减掉，减重复的要加回来呀^^

newkid

#17 Points

There are X points on a plain paper. Using three different colors, you will draw lines connecting each point with every other point. The condition is that none of the triangles formed by these connections would be monochromic.

What is the maximum possible value for X?

纸上有X个点，你用三种颜色的线把它们两两相连，条件是不能出现单色的三角形。X可能的最大值是多少？

lastwinner

原帖由 newkid 于 10-11-3 22:35 发表
#17 Points

There are X points on a plain paper. Using three different colors, you will draw lines connecting each point with every other point. The condition is that none of the triangles formed by these connections would be monochromic.

What is the maximum possible value for X?

纸上有X个点，你用三种颜色的线把它们两两相连，条件是不能出现单色的三角形。X可能的最大值是多少？

这个问题好玩，几个思路：
1、逐步推演。总是尽可能少的使用这几种颜色，从三个点开始推演，直到下一条线段必须用到第四种颜色才能保证包含该线段的三角形不是单色为止。此时就可以知道X的最大可能值。
2、抽屉原则。当一条线段为N个三角形共有时，该线段的颜色必须是第四种颜色，方可保证这N个三角形不出现单色，那么N的最小值加1就是X可能的最大值。当然这个要看平均的，如果单拿一条线段来看，完全可以让该线段是颜色A，其他N个点与该线段两端点的连线都是颜色B，看似同样能满足题设，但实际上你要将这N个点也互连，情况就不是那么简单了。

下面尝试来做一下，由1法，推到X＝5也满足后，脑子不够用了，得出X>=5


任取两种颜色构成三角形的两边，取法总共有C(3,2)=3种
任取一种颜色两次，构成三角形的两边，取法总共有C(3,1)=3种
假设上述3＋3＝6种情况下都没有任何两边重复，如果新增一条线段与上述的6组边相连接成三角形，那新增的这条线段必须是第四种颜色方能保证所组成的6个三角形中没有单色的
由2可知，此时的X＝6＋1＝7
不过这里的推算并没有证明按这种方法去做就能得到最大的X


睡觉了，再说

nlrte13

原帖由 newkid 于 2010-11-3 22:35 发表
#17 Points

There are X points on a plain paper. Using three different colors, you will draw lines connecting each point with every other point. The condition is that none of the triangles formed by these connections would be monochromic.

What is the maximum possible value for X?

纸上有X个点，你用三种颜色的线把它们两两相连，条件是不能出现单色的三角形。X可能的最大值是多少？

初步推算 X 不会超过16，还没有验证能不能达到16，猜测应该是可以达到的：D

lastwinner

原帖由 nlrte13 于 10-11-4 09:13 发表

初步推算 X 不会超过16，还没有验证能不能达到16，猜测应该是可以达到的：D

你是对的

圖論1.　 設 u1, u2, u3, u4, u5, u6 為平面上的相異六點, 且任三點不共線, 今將任二點的連接線段塗以紅色或是藍色,
求證：必出現兩個單色三角形。(註:所謂單色三角形, 意指以所給的六個點中之三個點為頂點, 且三邊為同一色的三角形。兩個單色三角形不一定要同色, 二者可以沒有共同頂點, 亦可以有共同頂點或共同邊。)證明1)我們先證:一定有一個單色三角形。
考慮 u1u2, u1u3, u1u4, u1u5, u1u6 這五個線段顏色。根據鴿籠原理, 其中必有三線段同色, 不失一般性, 設 u1u2, u1u3, u1u4 都塗成紅色。
接著看 u2u3, u2u4, u3u4 三個線段的顏色。情況一:u2u3, u2u4, u3u4 都塗藍色,
則有藍色三角形 u2u3u4。情況二:u2u3, u2u4, u3u4 有一為紅色, 不失一般性, 設 u2u3 為紅色。
則有紅色三角形 u1u2u3。(2)現在證:必有兩個單色三角形。

現在看 u4u5, u4u6, u5u6 的顏色。
情況一:u4u5, u4u6, u5u6 皆為紅色。
則我們有了第二個單色三角形 u4u5u6。情況二:
我們看 u4u1, u4u2, u4u3 的顏色。此三線段, 必有兩個同色。設 u4u1, u4u2 同色。再分情況討論:情況二之1:u4u1, u4u2 皆為紅色,

情況二之2:u4u1, u4u2 皆為藍色,
若 u5u1 或 u5u2 為藍色, 則我們有藍色三角形 u1u4u5 或藍色三角形 u2u4u5 (∵(Ⅱ))
若 u5u1 及 u5u2 皆為紅色,










3.　 平面上有 17 點, 任三點不共線, 今在任二點之間的線段著以紅色或綠色或藍色。
求證：必有單色三角形出現。證明:設此 17 點為 v1, v2, v3,..., v17。我們看下列 16 個線段所著的顏色: v17v1, v17v2, v17v3, v17v4,..., V17v16。此 16 線段中, 至少有 6 個線段著以相同顏色; 我們設 v17v1, v17v2, v17v3,..., v17v6 都著紅色。我們考慮兩種情況:情況一:某一線段 vivj(1 i < j 6) 為紅色。
則我們有一紅色三角形 v17vivj 。情況二:所有 vivj(1 i < j 6) 都非紅色。

newkid

二位很强大，什么题都难不住。

lastwinner

我是搜的，我没想明白  鸽笼原理 怎么在这里应用
看了别人的解答后，恍然大悟……

nlrte13

看鹦鹉哥的贴图，《破冰》终于出炉了啊^^

nlrte13

原帖由 newkid 于 2010-11-4 22:50 发表
二位很强大，什么题都难不住。

神经元那题就难住了 - -#

等啥时候有大量空闲时间，再好好研究下^^