In graph theoretical language, consider a graph $G$ where friendship relationships are its edges. If $\chi(G) = n$ (the chromatic number of $G$), and we consider such a colouring of $G$ with colours $c_1,c_2,\ldots,c_n$, then there exists a rainbow path $x_1x_2\ldots x_n$ such that the colour of $x_k$ is $c_k$, for $1\leq k \leq n$. Denote by $V_1\neq \emptyset$ the set of vertices coloured $c_1$, and for $2\leq k \leq n$ denote by $V_k$ the set of vertices coloured $c_k$ and having at least a neighbour coloured $c_{k-1}$. We claim $V_k \neq \emptyset$ for all $2\leq k \leq n$. Indeed, let $m$ be the first index with $V_m = \emptyset$. Recolour the vertices in $V_k$ with $c_{k+1}$ for $1\leq k \leq m-1$. This new colouring would only use $n-1$ colours, contradicting $\chi(G) = n$. But now, start with $v_n\in V_n$, then pick $v_{n-1}\in V_{n-1}$ such that $v_{n-1}v_n$ is an edge, then pick $v_{n-2}\in V_{n-2}$ such that $v_{n-2}v_{n-1}$ is an edge, and so on. We obtain a rainbow path $v_1v_2\ldots v_n$. I have presented this proof only so that my answer is self-contained. The question has already been asked and answered on AoPS in 2011; see http://www.artofproblemsolving.com/community/q1h402094p2241883.

Here's an outline of my proof. Pick a random student from column 1 and mark him as $M_1$. Mark one of his friend of column 2 as $M_2$. Now mark one of the $M_2$'s friend of column 3 as $M_3$ and so on. After certain amount of moves we would have to stop with this. Let $M_1, M_2,...,M_k$ be the such created sequence. If $k=n$ we're done. Otherwise move $M_k$ to the $(k+1)-th$ column. Note that since $M_k$ doesn't have a friend in the $(k+1)-th$ column moving him to that column will maintain the "good" configuration. Now create a new $M_1, M_2,...,M_k$ sequence and repeat the mentioned algorithm. If we don't find such a sequence of length $n$, then after a certain amount of repeating this algorithm there would be a column that has no students in it. This will eventually happen since the number of students is finite and we're moving students from left to right (if we denote column 1 as the left-most column). But this is impossible because of the condition. Also this algorith must terminate and the only way to do that is to find a sequence of length $n$, which means we must have find such a sequence after certain tries. Hence the proof. P.S. In other words this proves that $\not \exists M_1,M_2,M_3,...,M_N \implies $ "good" configurations for (n-1) columns. The other side is trivial so we must have $\not \exists M_1,M_2,M_3,...,M_N \iff $ "good" configurations for (n-1) columns. But since the right side doesn't hold the left side doesn't hold too. Q.E.D.

Here is a proof by induction: We say that a configuration of contestants is "$n$-good" if it is a "good" configuration in $n$ columns but the contestants can't be redistributed in a "good" configuration with strictly less than $n$ columns. We will prove by induction that every "$n$-good" configuration has a sequence of contestants that satisfies the condition of the problem. For the base case, we take $n = 2$. Let the columns be numbered $1$ and $2$. If $A_{2}$ is the set of all contestants in column $2$ that have a friend in column $1$, then $A_{2}$ must not be empty. If it were empty, then we could move all the contestants from column $2$ to column $1$ and get a "good" configuration with less columns, which is a contradiction. Now suppose that we have a "$n+1$-good" configuration. Enumerate the columns by $1$, $2$, ..., $n+1$. Let $A_{n}$ be the set of all contestants in the column number $n$ that have a friend in column $n+1$. We move all contestans from column $n$ not in $A_{n}$ to column $n+1$. Note that $A_{n}$ must not be empty because the configuration is "$n+1$-good". Now we get a new "$n+1$-good" configuration, such that every contestant in column $n$ has a friend in column $n+1$. Note that the configuration consisting of the columns $1$ to $n$ is a "$n$-good" configuration because the original configuration is "$n+1$-good". Now by induction we have that there is a sequence of friends satisfying the condition of the problem starting in column $1$ and ending in column $n$. Because every contestant in column $n$ has a friend in column $n+1$, we take the last contestant in the sequence, who is in column $n$, and add his friend from column $n+1$ to the sequence. Hence, the proposition of the problem is proved by induction.

Define the graph $G$ which has a directed edge from person $i$ to person $j$ iff $i$ is friends with $j$ and column of person $i$ is less than column of person $j$. For two people $i$ and $j$, person $i$ is inferior to person $j$ if they are linked by some path in $G$. We are given that the minimum number of antichains required to partition the contestants is at least $n$ (we need $n$ just to not have $2$ friends in the same antichain and these are clearly linked). Thus, the max chain length is also at least $n$, and it follows that there exist a chain $c_1, \dots, c_n$ with $n$ contestants. Consider in order all the vertices involved in some path from $c_i$ to $c_{i + 1}$ in this chain (so $c_0, v_1, \dots, v_k, c_1, \dots$). Take the first $n$ to get the desired group. EDIT: Rip doing problems in AP Government