2021 年广西预赛

解答

先证 $n=17$ 一定满足。任取一名同学 $X$，他与其余 $16$ 人的边中至少有 $6$ 条同色， 不妨设与集合 $S$ 中的 $6$ 人都讨论问题 $A$。若 $S$ 内有一对也讨论 $A$，便与 $X$ 组成所求三人组；否则 $S$ 内的完全图只使用颜色 $B,C$。任取 $S$ 中一点，它连向其余 五点的边至少有三条同色；若这三个端点之间有一条边也是该色，便组成同色三角形， 否则这三个端点之间的三条边全为另一色，也组成同色三角形。因此 $17$ 人时必然出现 所求三人组。

下面说明 $16$ 人还不能保证。取有限域

其非零元素构成阶为 $15$ 的循环群。取一个生成元 $g$，令 $H=⟨g^3⟩$， 则 $H$ 是阶 $5$ 子群，且 ${\mathbb{F}}_{16}^{\times }$ 分成三个陪集 $H,gH,g^{2}H$。 以域中 $16$ 个元素为同学；对不同的 $x,y$，按 $x-y$ 落在哪个陪集给边着三种颜色。

该染色没有单色三角形。否则某个单色三角形的三条差经同乘一个非零常数后， 可写成 $u,v,u+v\in H$。令 $t=v/u\in H$，则 $1+t\in H$。于是 $t^5=(1+t{)}^5=1$。在特征 $2$ 下

从而 $t+t^4=1$。另一方面，$t\in H$ 且 $t\ne 1$，故 $t^4+t^3+t^2+t+1=0$。两式相减得 $t^3+t^2=0$，即 $t=1$，矛盾。 故 $16$ 人存在无单色三角形的安排。

综上，最小值为