67th 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 \cdots \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\ne 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.