Combinatorial problem about $n \times 3$-matrix Let $A$ be an $n \times 3$-matrix so that for each number $k \in \{1,2,3\}$ there are exactly $n$ entries $a_{ij}$ s.t. $a_{ij}=k$. Is it possible to rearrange the entries of each column of $A$, such that in every row every number appears at least once?
I was trying to prove this via pidgeonhole principle, but I didn't get far. Clearly, there are $3n \choose n,n,n$ possibilities for such matrices, but this didn't help. 

More generally this works if you have an $n \times m$ matrix with $n$ entries $a_{i,j}$ such that $a_{i,j} = k$ for $k = 1, 2, \dots m$.
First note that if we are able to rearrange the columns to make a single row have one of each entry, we can just remove that row and we are left with an $(n-1)\times m$ matrix with the same condition.  So inductively we just need to show we can do it for a single row.
Now consider the bipartite graph on $m+m$ vertices labeled "columns" and "entries", where a column $j$ gets connected to entry $k$ by an edge if the $j$th column contains an entry with value $k$.  Being able to rearrange the columns to have a row with distinct entries is the same as finding a matching on this graph.
But now we can test Halls matching criterion:  Any collection of $a$ columns must be connected to at least $a$ entry values because they have $a \times m$ total entries but $(a-1)$ values can only use up $(a-1) \times m$ positions by assumption. Therefore such a matching exists.
