Library / /109 of 133

, 2015

Combinatorics Difficulty 6.6 National olympiad Prove it Saudi Arabia

The total number of languages used in KAUST is $n$ . For each positive integer $k \leq n$ , let $A_{k}$ be the set of all those people in KAUST who can speak at least $k$ languages; and let $B_{k}$ be the set of all people $P$ in KAUST with the property that, for any $k$ pairwise different languages (used in KAUST), $P$ can speak at least one of these $k$ languages. Prove that

a. If $2k \geq n+1$ then $A_{k} \subseteq B_{k}$ ;

b. If $2k \leq n+1$ then $A_{k} \supseteq B_{k}$ .

Solution

Let $\mathcal{L}$ be the set of all the languages used in KAUST.

a.
Assume $2k \geq n+1$ . Consider $P \in A_{k}$ , and let $\mathcal{L}_P \subseteq \mathcal{L}$ be the set of all languages spoken by $P$ . The set $\mathcal{L}_P$ contains at least $k$ languages.

Let $\mathcal{L}' \subseteq \mathcal{L}$ be a set of $k$ languages. We have
$|\mathcal{L}_P \cap \mathcal{L}'| = |\mathcal{L}_P| + |\mathcal{L}'| - |\mathcal{L}_P \cup \mathcal{L}'| \geq 2k - |\mathcal{L}| = 2k - n \geq 1.$
This means that $\mathcal{L}_P \cap \mathcal{L}' \neq \emptyset$ and therefore $P$ can speak at least one language in $\mathcal{L}'$ . Hence $P \in B_{k}$ .

b.
Assume $2k \leq n+1$ . Consider $P \in B_{k}$ , and let $\mathcal{L}_P \subseteq \mathcal{L}$ be the set of all languages spoken by $P$ and $\mathcal{L}' = \mathcal{L} \setminus \mathcal{L}_P$ . Because there is no language in $\mathcal{L}'$ spoken by $P$ we have $|\mathcal{L}'| \leq k-1$ . We deduce that
$|\mathcal{L}_P| = |\mathcal{L}| - |\mathcal{L}'| \geq n - (k-1) \geq k.$
This means that $P$ speaks at least $k$ languages and therefore $P \in A_{k}$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.