NMO Selection Tests for BMO and IMO

A choice function or simply a choice for the collection $S_1, \dots, S_n$ is a function $c$ from the first $n$ positive integers to the union $S_1 \cup \dots \cup S_n$ such that $c(i)$ is a member of $S_i$ for each $i$. We must show that an injective choice is always possible under the conditions in the statement. To this end, we prove that the number of non-injective choices is strictly less than $|S_1| \cdots |S_n|$, the total number of possible choices.

Indeed, a non-injective choice function sends some $i$ and some $j \neq i$ to the same element necessarily lying in $S_i \cap S_j$, so the number of non-injective choices does not exceed
$$\sum_{1 \le i < j \le n} |S_i \cap S_j| \; |S_1| \cdots |\hat{S}_i| \cdots |\hat{S}_j| \cdots |S_n| = |S_1| \cdots |S_n| \sum_{1 \le i < j \le n} \frac{|S_i \cap S_j|}{|S_i| |S_j|} < |S_1| \cdots |S_n|;$$
where the hat over $S_i$ and $S_j$ means that these sets are to be omitted. The conclusion follows.