Title

$9$ 位数学家,其中每 $3$ 位数学家中至少有 $2$ 位会说同一种语言,并且每位数学家至多会说 $3$ 种语言,问:

  1. 证明:存在某种语言,其至少被 $3$ 位数学家掌握;

  2. 如果其它条件不变,数学家的数量变为 $8$ 人,结论是否还成立?

Solution

Agreement of Signs

记数学家的集合为 $\{p_{1}^{}, p_{2}^{}, \dots, p_{9}^{}\}$, 语言的集合为 $\{l_{1}^{}, l_{2}^{}, \dots, l_{n}^{}\}$, 共有 $n$ 种语言;

称 数学家 $p_{i}^{}$ 和数学家 $p_{j}^{}$ 有共同语言,当且仅当存在至少一门语言被这二人共同掌握。

Solution to Question 1

考虑命题:任意两名数学家都有共同语言。

  1. 若此命题成立

    则不妨设某位数学家 $p_{1}^{}$ 掌握 $i$ 种语言 $\{l_{1}^{}, \dots, l_{i}^{}\}(1 \leq i \leq 3)$, 于是对于其他 $8$ 位数学家,他们都至少掌握 $\{l_{1}^{}, \dots, l_{i}^{}\}$$i$ 种语言中的一种.

    于是根据抽屉原理,这 $i$ 种语言中存在某种语言,在剩下的数学家中被至少 $\lceil \frac{8}{i} \rceil \geq \lceil \frac{8}{3} \rceil = 3$ 位数学家掌握;再算上数学家 $p_{1}^{}$ 本人,至少有 $4$ 人掌握了这门语言,于是我们得到了比欲证命题更强的结论。

  2. 若此命题不成立

    则不妨假设存在两位数学家,记作 $p_{1}^{}$$p_{2}^{}$ ,他们没有共同语言,他们各自掌握的语言的集合记作 $L_{1}^{}$$L_{2}^{}$.

    注意此二人没有共同语言,因此我们有

    $$L_1 \cap L_2 = \varnothing \\ 2 \leq \lvert L_1 \cup L_2 \rvert = \lvert L_1 \rvert + \lvert L_2 \rvert \leq 6$$

    而此时除了此二人之外,另外还有 $7$ 名数学家;剩下的数学家中的每一位都必须掌握 $L_1 \cup L_2$ 中的至少一门语言,否则将与条件 “每 $3$ 位数学家中至少有 $2$ 位会说同一种语言” 矛盾。

    注意到 $7 > 6 \geq \lvert L_1 \cup L_2 \rvert$, 由抽屉原理可知,必定有一门语言被(剩下数学家中的)至少 $2$ 位数学家掌握;再算上 $p_{1}^{}$$p_{2}^{}$ 中之一自身 ,该语言至少有 $3$ 人掌握。

综合以上讨论,命题得证。

Q.E.D.

Solution to Question 2

此时结论不成立

如下图所示,字母表示数学家,整数表示语言;字母与整数间存在连线,当且仅当该字母所代表的数学家掌握该整数表示的那种语言。

G A A 1 1 A--1 2 2 A--2 3 3 A--3 B B 1--B C C 2--C D D 3--D 4 4 B--4 5 5 B--5 C--5 6 6 C--6 D--4 D--6 E E 7 7 E--7 8 8 E--8 9 9 E--9 F F 7--F G G 8--G H H 9--H 10 10 F--10 11 11 F--11 G--11 12 12 G--12 H--10 H--12

可以验证:这个构造 “刚刚好” 地使得结论不成立

  1. 每位数学家都恰好掌握 $3$ 门语言;

  2. $3$ 位数学家中至少有 $2$ 位会说同一种语言:

    • 这个性质的论证可以叙述如下:

    • 注意到:上图是由两个极大连通子图构成的图。任选 $3$ 位数学家,根据抽屉原理可知,其中必有两位处于同一个连通分量中;而处于同一个连通分量的任意两位数学家都恰好有一门共同语言;因此,题设的条件得到满足。

  3. 每种语言都恰好$2$ 位数学家掌握。

Note

笔者在碰见本问题的时候,精神状态不太好,能独立做出这个 solution,一部分真是灵感和运气的功劳。

并且此问题貌似还有另解,日后可能继续补上。