2010年德国数学奥林匹克第三题
发布网友
发布时间：2024-05-10 01:13
共3个回答
热心网友
时间：2024-05-14 07:51
.....
（看 书的时候忽 然想到了这 个题，于是 便借助书上 的定理给出 了一个证明 ，有些啰嗦 ，但自己觉 得没问题， 如有错
误， 或者说不清 楚的地方， 烦请指正。）
解答 首先需要用 到Ramsey定理 的无限式：
对任 意给定的r ，k ∈N * ，无限 集A ，以及A 的 全部r 元子集 的 任一k 染色，无 限集A 必有无 限子集X ，使 X 的全部r
元子 集 是单 色的。
……（*）
先证 明原题：
假设 存在一个方 案使作者的 要求能够得 到满足，即 此方案对任 意一个无限 子集X ，均存 在r使 得有r 人同时召开 过会
议， 也存在r 人从未召 开过会议。
约定 ：下面的i [n ] ，i，j 均是指矮 人编号。
记r [ t] 代表N * 的某个无限 子集中满足 “ 存在r 使得有r 人同时召 开过会议， 也存在r 人从未召 开过会议”
中的 r的最 大值，
不失 一般性，记 r[ 0] 是所有 大于2 的r[ t] 中最小 的一个（最 小数原理）
则X [ 0 ]中不存 在多于r [0 ] 人的集会。 ……………………………………（1 ）
（假 设X [0 ]中 存在一个r [ 0] +t （t ∈N *） 人的集会 ，由于X [ 0] 中存在r [0 ] 人从未召开 过会议，向 这r[ 0 ]人中 任意添
加t 人，则 这r[ 0 ]+ t人显 然也不能同 时召开会议 ，这样，r [ 0] +t 也是符 合要求的r ，而r > r[ 0] ，与r [0 ] 的定义矛
盾！）
对任 意 i [1 ]，i [2 ] ，…，i[ r [0 ]]∈X [0 ]， 将ij 连线并按如 下规则则染 色：
i [1 ]， i[2 ] ，…，i [r [0 ]] 共同 召开过会议 ： i[ 1 ]，i [2 ]， …，i[ r[ 0 ]] 染红
i [1 ]， i[2 ] ，…，i [r [0 ]] 从未 共同召开过 会议： i [1 ] ，i[ 2] ，…，i [r [0 ]] 染 蓝
在（*）中 令k =2 ，r = r[ 0] ，知X [ 0] 中必存在 无限子集Y 使得 Y是 单色的。
显然 ，Y 不能是红色 的，否则Y 中不 存在多于r [ 0] 个人的集 会（由（1 ））
故Y 是蓝 色的，因而 Y中 不存在任意 r[ 0] 人同时 参加集会
故Y 中任 意集会的人 数小于r [0 ]。
注意 到Y 也是N 的子集 ，故存在r 使得有 r人同 时召开过会 议，也存在 r人从 未召开过会 议。
而r < r[ 0 ]，故在 **Y 中r =2
由（ 1） 的讨论知Y 中不 存在多于3 人的集 会
对Y 中任 意i，j ，若i ，j共同 开会，将其 染红，否则 染蓝。
对Y 使用 （*），令r =k = 2 ，知Y 中有单色 无限子集T 。
显然 矛盾！（若 为红，则T 中任 意两个人都 开过会，否 则T 中任意2 人都未 开会，与假 设矛盾！）
故假 设不成立， 即作者的要 求不能满足 。
（*）证明 ：
对任 意给定的r ，k ∈N * 以及 无限集A 的全 部r元 子集 的 任一k 染色，无 限集A 必有无 限子集X ，使 X 的全部r 元子集
是单 色的。
为方 便书写，将 X 所有的t 元子集记为 X {t }，X [ s] 所有的 t元子集 记为X [s ] {t }，X - Y 代表X 中所有不 属于Y 的元素构
成的 **
对r ∈N * 进行归 纳：r =1 时，此 即为抽屉原 理的无限形 式。
现设 r> 1 ，记A { r} 的k 染色是f ：A { r}→ { 1， 2， 3，… ，k }
在A 中 任取一元x [ 1 ]，记A - {x [ 1 ]}=B [ 1]。 从A { r} 的k 染色f 可按如下 方式产生B [ 1] { r- 1} 的一个k 染色 f[ 1] ：对B
[ 1] 的r -1 元子集S ，定 义f[ 1] （S ）= f（S ∪{ x 1 }），
根据 归纳假设， 有某一个i [1 ]∈ {1 ，2 ，3 ，…，k } 以及B [1 ] 的一个无限 子集A [ 1] ，使得A [ 1 ]{ r- 1} 在染色 f[ 1] 下是
i [1 ]色 的。改记A = A [ 0] ，则上面 的步骤可简 单的表示为 ：
x [ 1]∈ A [ 0] ，A [0 ] -{ x [1 ]}=B [ 1] A [ 1] ，A [ 1] 无限，
A [ 1] { r- 1} f [1 ]^(- 1) (i [1 ]) ，i [1 ]∈ {1 ，2 ，3 ，…，k }。
如此 重复得到
x [ n]∈ A [ n- 1 ]，A [ n -1 ]- {x [ n]}= B [n ] A [n ] ，A [n ] 无限，
A [ n ]{ r- 1} f [n ]^( -1 )( i[ n]) ， i[n ]∈ { 1，2 ，3 ，…， k}。
这样 我们得到了 3个 无穷序列： {i [n ]： n∈ N *}{x [ n ]：n ∈N *}{ A [ n] ：n ∈N *}。
由抽 屉原理，i [n ] 中必有无穷 多项相等， 记为i[ n [1 ]]= i[n [ 2]]= i[ n [3 ]]=……
不妨 设i[ n [1 ]]=i [n [ 2]]= i[ n [3 ]]=…… =1 。记X = { x[ n [t ]] |
t ∈N *}则由 定义及数学 归纳法，易 知其在f 下是1 色的。
-_-!!!
热心网友
时间：2024-05-14 07:52
第一页引入第一个矮人A时，上述条件当然不成立，因为根本不存在＂两个以上矮人＂的集合。
第二页再引入一个矮人B时，上述条件仍然不成立，因为A与B若不是互相开过会，就是没有。
第三页以後就可以永远成立了，你让矮人集合（A、C）开过会，而让矮人集合（B、C）永远互不照面，这样不就结了？未来的矮人DEF。。。都没有影响啊。
不懂。
热心网友
时间：2024-05-14 07:52
