Macedonian Mathematical Olympiad

We will perform a rearrangement with respect to columns. First we move to the first column each contestant from the second column who doesn't have an acquaintance in the first column. (1 point) The new arrangement is “well”, and therefore at least one contestant remains in the second column. Now we move to the second column each contestant from the third column who doesn't have an acquaintance among the remaining contestants in the second column. The new arrangement is “well”, and therefore there is at least one contestant remaining in the third column. We continue this procedure. (3 points) In the end we move to the $(n-1)$-th column each contestant from the $n$-th column who doesn't have an acquaintance among the remaining ones in the $(n-1)$-th column. The new arrangement is again “well” and therefore at least one contestant remains in the $n$-th column. We denote such a contestant by $M_n$. (1 point) He must have an acquaintance $M_{n-1}$ in the $(n-1)$-th column. Let us notice that $M_{n-1}$ has not been moved (otherwise the initial arrangement is not “well”). Therefore $M_{n-1}$ has an acquaintance $M_{n-2}$ in the $(n-2)$-th column. We conclude analogously that $M_{n-2}$ has not been moved. We proceed in this way and therefore we find contestants $M_1,M_2,\dots ,M_n$ for which (1) and (2) hold. (3 points)