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. 
 A: The answer is yes!
Proof by construction:


*

*leave the first column as is

*start with row 1 and repeat the following until you can't: 


*

*find the two missing numbers for each row in the 2'nd and 3'rd column (order doesn't matter) and move them up.

*move to the next row



If the algorithm ends after the last row, it will construct your answer. Suppose that it ends after row $i < n$. This happens if you need a digit $d$ that you cannot find in either of the 2nd or 3rd columns. Since there are total $n$ copies of digit $d$, and the first $i$ rows have only $i$ copies, there are $n - i$ copies left, which all have to be in column 1. That means the rest of the rows have the digit $d$ in their first column and do not need a digit $d$, which is a contradiction.
A: 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.
