medium | discrete |

A group has 70 members. For any two members $X$ and $Y$ there is a language that $X$ speaks but $Y$ does not, and there is a language that $Y$ speaks but $X$ does not. At least how many different languages are spoken by this group?

8 choose 4 $= \binom{8}{4} = 70$

This group has at least 8 different languages.

Let's go with hit and trial.

- Everyone knows the same language, that is a contradiction. Therefore it must be more than 1 language.
- 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.
- 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.

- 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 |

- 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