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

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

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

事实上，这道题就是要证明拉姆塞数𝑟(3,3,3)=17．𝑟(3,3,3)≥17由抽屉原理容易证明，也就是第六届IMO的第4题：

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

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

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

若𝑥,𝑦∈𝐺，易知𝑥+𝑦∈𝐺．用𝑥+𝑦∈𝑉_(𝑖)(𝑖=1,2,3)表示同学𝑥和同学𝑦讨论第𝑖个问题；用𝑥∈𝑉_(𝑖)(𝑖=1,2,3)表示同学0000和同学𝑥讨论第𝑖个问题．

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

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

设𝑓(𝑥)=𝑥^(4)+𝑥+1是域𝐹:=ℤ_(2)={0,1}上的多项式，显然𝑓(𝑥)在𝐹上不可约．设𝛼为𝑓(𝑥)的一个根，则存在𝐹的单纯代数扩域𝐹(𝛼)，𝐹(𝛼)的一切元均可表为

因𝐹:=ℤ_(2)={0,1}，所以𝐹(𝛼)中有2^(4)=16个元素，即

其中，𝛼在𝐹上的极小多项式为𝑓(𝑥)，且

利用（1）式知

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

为循环群．

作陪集

设是𝐹(𝛼)的一个二元子集．定义映射𝜑:𝑄→{1,2,3}，满足

则对任意固定的𝑖，不可能存在𝐹(𝛼)的三元子集𝑈使得𝑈⊆𝜑^(−1)(𝑖)．不失一般性，我们不妨设

由