Problem

Source: 2019 Brazil Ibero TST P2

Tags: combinatorics



We say that a distribution of students lined upen in collumns is $\textit{bacana}$ when there are no two friends in the same column. We know that all contestants in a math olympiad can be arranged in a $\textit{bacana}$ configuration with $n$ columns, and that this is impossible with $n-1$ columns. Show that we can choose competitors $M_1, M_2, \cdots, M_n$ in such a way that $M_i$ is on the $i$-th column, for each $i = 1, 2, 3, \ldots, n$ and $M_i$ is a friend of $M_{i+1}$ for each $i = 1, 2, \ldots, n - 1$.