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

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

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

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

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

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

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

公式：V_1=\{1100,0011,1001,1110,1000\}，

公式：V_2=\{1010,0101,0110,1101,0100\}，

公式：V_3=\{0001,0010,0111,1011,1111\}．

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

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

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

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

公式：a_0+a_1\alpha+a_2\alpha^2+a_3\alpha^3(a_i\in F,i=0,1,2,3)

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

公式：F(\alpha)=\{0,1,\alpha,\alpha+1,\cdots,1+\alpha+\alpha^2+\alpha^3\}

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

利用（1）式知

公式：F(\alpha)=\{0,1,\alpha,\alpha^2,\alpha^3,\cdots,\alpha^{14}\}——（2）

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

公式：\begin{align*} &H_1:=H=(\alpha^3)=\{1,\alpha^3,\alpha^6,\alpha^9,\alpha^{12}\}\\ =&\{1,\alpha^3,\alpha^3+\alpha^2,\alpha^3+\alpha,\alpha^3+\alpha^2+\alpha+1\}\\ =&\{(1,0,0,0),(0,0,0,1),(0,0,1,1),(0,1,0,1),(1,1,1,1)\} \end{align*}

为循环群．

作陪集

公式：\begin{align*} &H_2:=\alpha H=\{\alpha,\alpha^4,\alpha^7,\alpha^{10},\alpha^{13}\}\\ =&\{\alpha,\alpha+1,\alpha^3+\alpha+1,\alpha^2+\alpha+1,\alpha^3+\alpha^2+1\}\\ =&\{(0,1,0,0),(1,1,0,0),(1,1,0,1),(1,1,1,0),(1,0,1,1)\} \end{align*}

公式：\begin{align*} &H_3:=\alpha^2 H=\{\alpha^2,\alpha^5,\alpha^8,\alpha^{11},\alpha^{14}\}\\ =&\{\alpha^2,\alpha^2+\alpha,\alpha^2+1,\alpha^3+\alpha^2+\alpha,\alpha^3+1\}\\ =&\{(0,0,1,0),(0,1,1,0),(1,0,1,0),(0,1,1,1),(1,0,0,1)\} \end{align*}

设公式：Q=\{(x,y)|x\neq y且x,y\in F(\alpha)\}是𝐹(𝛼)的一个二元子集．定义映射𝜑:𝑄→{1,2,3}，满足

公式：\varphi(x,y)=i\iff x+y\in H_i,i=1,2,3

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

由

公式：\varphi(x,y)=i\iff x+y\in H_i,i=1,2,3