2021年广西预赛题的构造思路

年广西预赛的最后一题为：

题目1 某校名同学通过选拔进入学校的数学讨论班．在一次讨论班上他们讨论、和三个问题．已知每位同学都和班里的其他所有同学讨论了其中的一个问题，每两位同学只讨论一个问题．若至少有名同学互相之间讨论的是同一个问题，求的最小值，并给出证明．

事实上，这道题就是要证明拉姆塞数．由抽屉原理容易证明，也就是第六届IMO的第题：

题目2 十七个人互相通信，每一个人都和其他人写信．在他们的信上一共讨论有三个不同的话题，每两个人只讨论一个话题，求证：这些人当中至少有三个人他们所讨论的话题是一样的．

而时反例的构造则不那么自然，参考答案如下：

当时，考虑二进制下的集合

若，易知．用()表示同学和同学讨论第个问题；用()表示同学和同学讨论第个问题．

按照上述规定，没有位同学互相之间讨论同一个问题．因此．

这个构造可能会让人摸不着头脑，其实它的背景是循环群．下面给出另一个证明：(来源：《Ramsey数的一种证法》 邵卫）

设是域上的多项式，显然在上不可约．设为的一个根，则存在的单纯代数扩域，的一切元均可表为

因，所以中有个元素，即

其中，在上的极小多项式为，且

利用式知

所以中的所有非零元素组成一个乘法群为循环群，记为．则子群

为循环群．

作陪集

设是的一个二元子集．定义映射，满足

则对任意固定的，不可能存在的三元子集使得．不失一般性，我们不妨设

由