逻辑推理，满足条件的$n\ge6$人聚会，求证其中必有三人两两相识

abababa

$n\ge 6$人聚会，满足

• 每人至少与其中$[\frac{n}{2}]$个人相识。
• 设集合$X$为其中任意$[\frac{n}{2}]$个人，集合$Y$为其余人，则或者$X$中有$2$人相识，或者$Y$中有$2$人相识。
  

求证这$n$个人中必有三人两两相识。其中$[x]$表示不超过$x$的最大整数。

下面是我的证明：
设这$n$个人构成的集合为$M，$对于$a\in M$，由于$a$至少与$[\frac{n}{2}]$个人相识，因此必存在$b$与$a$相识。

设集合$A$为所有与$a$相识的人中除$b$以外的$[\frac{n}{2}]-1$个，集合$B$为所有与$b$相识的人中除$a$以外的$[\frac{n}{2}]-1$个。假设存在$c\in (A\cap B)$，则$a,b,c$三人两两相识，命题成立。下面考察$A\cap B=\varnothing$的情况。

• 当$n$为偶数时，设$n=2k$，于是$|A|=k-1, |B|=k-1$，而$A\cap B=\varnothing$，因此$A\cup B=M \setminus \{a,b\}$。令集合$A'=(A\cup \{b\})$，集合$B'=M \setminus A'=(B\cup \{a\})$，由于$|A'|=k=[\frac{n}{2}]$，由条件知，或者$A'$中有$2$人相识，或者$B'$中有$2$人相识。若$A'$中有$2$人相识，注意$A\cap B=\varnothing$，因此$b$与$A$中任意一人都不相识，即$A'$中相识的$2$人必定没有$b$，设$A'$中相识的$2$人为$x,y$，从而$a,x,y$三人两两相识，命题成立。同理若$B'$中有$2$人相识命题也成立。
  
  于是当$n$为偶数时命题成立。
• 当$n$为奇数时，设$n=2k+1$，于是$|A|=k-1, |B|=k-1$，由于$A\cap B=\varnothing$而$|M|-|A|-|B|=3$，因此可设$M=A\cup B\cup \{a,b,c\}$。
  
  • 若$c$与$a,b$都相识，则$a,b,c$三人两两相识，命题成立。
  • 若$c$与$a,b$都不相识，当$A$或$B$中存在两人相识时，不妨设$x,y\in A$相识，则$a,x,y$三人两两相识，命题成立。否则$A$中的人互不相识，同理只要考察$B$中的人也互不相识的情况。
    
    设有$k_1$人与$a,c$都相识，$k_2$人与$b,c$都相识，则与$c$相识的人数为$k_1+k_2$，因此$k_1+k_2 \ge [\frac{n}{2}]$，不妨设$k_1 \ge k_2$，结合$n \ge 6$知$k_1 \ge 2$。假设$k_2=0$，即无人与$b,c$都相识，注意$B$中的人都与$b$相识，因此他们与$c$都不相识，但与$c$相识的人至少有$[\frac{n}{2}]$个，因此$A\cup \{a\}$中的人都与$c$相识，特别地$a,c$相识，这和$c$与$a,b$都不相识矛盾，因此假设$k_2=0$错误，于是$k_2 \ge 1$。由$k_1 \ge 2, k_2 \ge 1$可设$x,y$与$a,c$都相识，$z$与$b,c$都相识。若$z\in A$，则$a,z,b$三人两两相识，命题成立，若$x\in B$或$y\in B$，则$a,x,b$或$a,y,b$三人两两相识，命题成立，因此可设$z\in (M \setminus A)=(B\cup \{a,b,c\}), x,y\in (M \setminus B)=(A\cup \{a,b,c\})$。由于$B$中的人互不相识，因此$B$中无人与$z$相识，然而$z$至少与$[\frac{n}{2}]$个人相识，所以除$b,c$外，$z$还至少与$[\frac{n}{2}]-2$人相识，显然这$[\frac{n}{2}]-2$人都来自集合$A\cup \{a\}$。若$z$与$a$相识，则$a,z,b$三人两两相识，命题成立。否则$z$与$A$中的$[\frac{n}{2}]-2=k-2$人相识，但$|A|=k-1$，所以$z$至少与$x,y$之一相识，不妨设$z,x$相识，则$c,x,z$三人两两相识，命题成立。
  • 若$c$仅与$a,b$之一相识，不妨设$c,a$相识，令集合$A'=(A\cup \{b,c\})$，集合$B'=M \setminus A'=(B\cup \{a\})$，由于$|B'|=k=[\frac{n}{2}]$，由条件知，或者$B'$中有$2$人相识，或者$A'$中有$2$人相识。
    
    若$B'$中有两人相识，则这两人的情况只可能是$a,x, x\in B$或$x,y\in B$。若相识的两人为$a,x$则$a,x,b$三人两两相识，命题成立，若相识的两人为$x,y$则$x,y,b$三人两两相识，命题成立。若$A'$中有两人相识，则这两人的情况可能是$x,y\in A$或$b,x, x\in A$或$b,c$或$c,x, x\in A$。若相识的两人为$x,y$则$a,x,y$三人两两相识，命题成立，若相识的两人为$b,x$则$a,b,x$三人两两相识，命题成立，若相识的两人为$b,c$，这和$c$仅与$a$相识矛盾，若相识的两人为$c,x$，则$a,c,x$三人两两相识，命题成立。
    
    于是当$n$为奇数时命题成立。
    
  
  

但这个证明太长了，我觉得不够好，有没有什么更好的方法证明这种题？

lihpb

以前看过
画6个点组成正六边形，然后给每个点着色，后面的忘了

abababa

lihpb 发表于 2024-8-12 17:10
以前看过
画6个点组成正六边形，然后给每个点着色，后面的忘了

这是那个拉姆齐问题吧？和那个不太一样，那个只是6个点，这个是$\ge6$的任意n个点。

Czhang271828

给一个易于看懂的简答.

先转化作图论语言: 将人视作顶点, 相异顶点间有连边当且仅当两人相识.

证明采用反证法: 假设图中不含三角形, 导出矛盾即可.

讨论 1 假定 $n=2k$ 是偶数. 任取一条边 $x-y$, 则 $x$ 与 $y$ 没有公共邻点. 依照题设, $x$ 至少有 $k$ 个邻点, $y$ 亦然. 剩下的 $(2k-2)$ 个点必然划分作 $x$ 的 $(k-1)$ 个邻点与 $y$ 的 $(k-1)$ 个邻点. 因此, 图中所有的边仅存在于下图的双箭头处
$$
\begin{matrix}
\{x\} & \leftrightarrow & \{y\}\\[6pt]
\updownarrow &  & \updownarrow\\[6pt]
\text{$(k-1)$ 个 $x$ 邻点} & \leftrightarrow & \text{$(k-1)$ 个 $y$ 邻点}
\end{matrix}.
$$
记 $X$ 是 $x$ 的所有邻点, $Y$ 是 $y$ 的所有邻点, 则 $X$ 中无边, $Y$ 中亦无边. 矛盾.

讨论 2 假定 $n=2k+1$ 是奇数. 若某一点存在 $k+1$ 个邻点, 则解答同上. 故只需考虑所有点仅有 $k$ 个邻点的情形. 任取相邻的 $x-y-z$, 此时
$$
\begin{matrix}
\{x\} & \leftrightarrow & \{y\}&\leftrightarrow & z\\[6pt]
\updownarrow &  & \updownarrow &  & \updownarrow\\[6pt]
\text{$(k-1)$ 个 $x$ 邻点} & \leftrightarrow & \text{$(k-1)$ 个 $y$ 邻点} & &?
\end{matrix}.
$$
由于 $z$ 的 $(k-1)$ 个邻点不能包含 $y$ 的任一邻点, 从而 $z$ 与 $x$​ 有相同的邻点. 因此, 图中所有的边仅存在于下图的双箭头处
$$
\begin{matrix}
\{x,z\} & \leftrightarrow & \{y\}\\[6pt]
\updownarrow &  & \updownarrow\\[6pt]
\text{$(k-1)$ 个 $x$ 邻点} & \leftrightarrow & \text{$(k-1)$ 个 $y$ 邻点}
\end{matrix}.
$$

abababa

Czhang271828 发表于 2024-8-12 22:47
给一个易于看懂的简答.

先转化作图论语言: 将人视作顶点, 相异顶点间有连边当且仅当两人相识.

用反证法其实也没减少多少推理分支，但这个图的确非常直观。