Question 67
The contestants of this year's MMO are "well" distributed in $n$ columns (a distribution in columns is "well" if no two contestants in the same column are acquaintances), but the same cannot be obtained in less than $n$ columns. Show that there exist contestants $M_1, M_2, \dots, M_n$ for which the following hold:
(1) $M_i$ is in the $i$-th column, for each $i=1,2,\dots,n$;
(2) $M_i$ and $M_{i+1}$ are acquaintances, for each $i=1,2,\dots,n-1$.
(1) $M_i$ is in the $i$-th column, for each $i=1,2,\dots,n$;
(2) $M_i$ and $M_{i+1}$ are acquaintances, for each $i=1,2,\dots,n-1$.