2000年第26届俄罗斯数学奥林匹克十年级决赛试题

在矩形桌子上放着许多相等而不重合的正方体纸片，其边都平行桌子的边且被分别染成k(k>=2)种颜色之一。如果考虑任意k个颜色互不相同的正方形，那么它们中都有两个可用一枚钉子钉在桌上。证明：可用（2k-2）枚钉子把某一种颜色的所有正方形全部钉在桌上。

很难的题，很想弄懂，给个100分，谢谢了
三易巾凡,实在抱歉，你的答案我看得不太懂，能写具体些吗？

对颜色数k作归纳。假设k种颜色编号为C[1], C[2], ..., C[k]：
1. k = 2, 找出桌面上最左端的正方形s, 假设它的颜色为C[1], 则所有颜色为C[2]的正方形均与之相交, 并且这些正方形至少包含s右边的两个顶点之一, 从而可以用2个钉子钉住颜色为C[2]的所有正方形。
2. 设k = n时命题成立，k = n+1时，同样找出桌面上最左端的正方形s，假设它的颜色为C[n+1]，将除s外的所有颜色为C[n+1]的正方形除去，则剩下的k色正方形可以分成两类，一类和s相交(这些正方形至少包含s右边的两个顶点之一)，另一类满足:任k个颜色互不相同的正方形,存在两个正方形相交(否则这k个正方形和s组成的k+1个异色正方形两两不相交，矛盾)。第一类可用两个钉子钉住，第二类根据归纳假设可用2k-2个钉子钉住其中的某一色正方形，该色正方形即被2k-2+2 = 2(k+1)-2个钉子完全钉住。

试着排列一下
当k=2..
只有

1 2
2 1这种排列满足题意
正因为只要有12肯定满足，则增加第三个颜色时，直接是
k=3
1 2 3
2 1 3
3 3 3在最外层加3
依次类推当
k=4
1234
2134
3334
4444显然，最外层同色最多，且
只要在两个4之间钉钉就可以钉住7个四
用数学归纳法
假设k=n用2n-2个钉就够！
推出k=n+1时也成立，则结论成立

你哪里不懂啊 ？

queshi nan

难！

....................................

queshi nan
回答者：hgsfxy - 助理 二级 5-24 10:30

难！
回答者：67750402 - 兵卒 一级 5-24 20:51

....................................
回答者：ご☆锹栬伊亼 - 试用期 一级 5-24 20:53