第八次作业

1. (3.42.)

[!QUESTION]
一组人有 1900 人, 每个人至少有 1327 个朋友, 试证其中四位, 使得彼此都是好朋友.

我们通过鸽巢原理分步证明:

1. 任选一人 A, 其朋友集合 S 至少有 1327 人.
2. 分析 S 内部的朋友关系: 每个成员 $B\in S$ 在 整个图 中至少有 1327 个朋友.
   • B 的朋友包含 A 和 S 外的至多 572 人 (因外部共有 $1900-1-1327=572$ 人).
   • 因此, B 在 S 内部 至少有 $1327-1-572=754$ 个朋友.
3. 聚焦于一个成员 B 及其朋友: 任取 $B\in S$, 设其在 S 内的朋友集合为 T, $|T|⩾754$.
4. 分析 T 内的共同朋友: 任取 $C\in T$，C 在 S 内部 至少有 754 个朋友.
   • C 的朋友在 T 内至少有 $754-(1327-754)=181$ 人 (因 $S\setminus T$ 最多有 $1327-754=573$ 人).
   • 因此, C 在 T 中至少有 181 个朋友.
5. 应用鸽巢原理:
   • B 的朋友集合 T 有 754 人, C 在 T 中至少有 181 个朋友.
   • 必存在 $D\in T$, 使得 D 是 B 和 C 的共同朋友 (因 B 与 C 的共同朋友数 $⩾181$).
   • 此时，A、B、C、D 两两均为朋友, 构成 $K_4$.

2. (3.44.)

[!QUESTION]
单位圆圆周上任意 $n+1$ 个不同的点至少存在两点, 其间距离不超过 $2\sin \frac{\pi }{n}$.

将单位圆的圆周分成 $n$ 个等长的弧, 每个弧对应的圆心角为 $\frac{2\pi }{n}$. 根据鸽巢原理, 当在圆周上放置 $n+1$ 个点时, 至少有两个点落在同一个弧上.

设这两个点位于同一弧的两端, 其弦长最大为 $2\sin \frac{\pi }{n}$ (由弦长公式 $2r\sin \frac{\theta }{2}$, 其中 $r=1$, $\theta =\frac{2\pi }{n}$). 因此, 这两点的距离不超过 $2\sin \frac{\pi }{n}$.

3. (3.45.)

[!QUESTION]
边长为 1 的正方形内任取 9 点, 试证存在 3 个不同的点, 由此构成的三角形面积不超过 $\frac{1}{8}$.

将边长为 1 的正方形分成四个边长为 $\frac{1}{2}$ 的小正方形. 根据鸽巢原理, 9 个点中至少有一个小正方形包含至少 3 个点. 在该小正方形中, 任意三点形成的三角形面积最大不超过小正方形面积的一半, 即 $\frac{1}{2}\times {\left(\frac{1}{2}\right)}^2=\frac{1}{8}$. 因此, 存在三个点构成的三角形面积不超过 $\frac{1}{8}$.

4. (3.46.)

[!QUESTION]
任给 5 个整数, 试证其中必存在 3 个数的和被 3 除尽.

根据鸽巢原理, 将五个整数按模 3 的余数分为三类 (余 0、余 1、余 2), 可能出现以下两种情况:

1. 某一余数类至少包含三个数: 若存在余数类 (如余 0、余 1 或余 2) 包含至少三个数, 则这三个数的和必然能被 3 整除. 例如, 若三个数余 0, 则它们的和为 $0+0+0\equiv 0(\mathrm{mod}3)$; 若三个数余 1, 则和为 $1+1+1\equiv 3\equiv 0(\mathrm{mod}3)$; 同理, 余 2 的情况类似.
2. 每个余数类最多包含两个数: 此时余数分布必为 $2,2,1$ (例如余 0 和余 1 各两个数, 余 2 一个数). 此时, 选取余 0、余 1、余 2 各一个数, 其和为 $0+1+2=3\equiv 0(\mathrm{mod}3)$, 满足条件.

综上, 无论余数如何分布, 五个整数中必存在三个数的和被 3 整除.