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. 

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.
