多语言群体

至少 8 种语言。

把每个人会说的语言集合记为集合 $S_i$。题设对任意 $X,Y$ 都存在语言在 $S_X\setminus S_Y$ 中，等价于

• 对任意 $X\ne Y$，$S_X$ 不可能是 $S_Y$ 的子集。

因此 $\{S_i\}$ 在“集合包含”偏序下构成一个 反链（antichain）。

若总共有 $m$ 种语言，则反链的最大规模由 Sperner 定理给出：

$$\max |\text{antichain}| = \binom{m}{\lfloor m/2\rfloor}.$$

需要 $\binom{m}{\lfloor m/2\rfloor} \ge 70$。

• $m=7$ 时最大为 $\binom{7}{3}=35<70$。
• $m=8$ 时最大为 $\binom{8}{4}=70$。

所以至少需要 8 种语言（且可以达到）。

---

Original Explanation

This group has at least 8 different languages.

Solution

Let's go with hit and trial.

1. Everyone knows the same language, that is a contradiction. Therefore it must be more than 1 language.
2. So, $P_1$ knows one language and $P_2$ knows another language. But $P_3$ will know the same language as either $P_1$ or $P_2$. We cannot extend this to 3 people.
3. Might be true, but it is hard to confirm.

Let's try a different approach. Let's calculate the largest group possible, given the number of languages.

3. If there are three languages ($L_1, L_2, L_3$), we can construct the following table.

	$L_1$	$L_2$	$L_3$
$P_1$	knows
$P_2$		knows
$P_3$			knows

4. If there are four languages ($L_1, L_2, L_3, L_4$), we can construct the following table.

	$L_1$	$L_2$	$L_3$	$L_4$
$P_1$	knows
$P_2$		knows
$P_3$			knows
$P_4$				knows

This is decent, but I think we can do better by assigning more than one language to each person.

	$L_1$	$L_2$	$L_3$	$L_4$
$P_1$	knows	knows
$P_2$	knows		knows
$P_3$	knows			knows
$P_4$		knows	knows
$P_5$			knows
$P_6$		knows		knows

Now, there are $6$ people, because we assigned two languages. The number 6 is coming from choosing $2$ from $4$, i.e. $\binom{4}{2} = 6$

Note that if we assign the same set of languages to two people (say: $L_1$ & $L_2$) then these two members will fail the desired criteria. Therefore we have to choose different sets of languages for each member, and one set cannot even be a subset of another set.

Also, note that the term $\binom{n}{x}$ takes the maximum value for $x = n/2$.

Therefore, the maximum number of people for a given number of languages is $\binom{n}{n/2}$, where $n$ is the number of languages.

Now, looking at the original question, $70 = \binom{8}{4}$, i.e. the maximum number of languages is $8$, and the maximum number of languages that one person knows is $4$.

Note that we can also