Mathematical Olympiad Rioplatense

The maximum $n$ is $9$. An example with $n=9$ is the table to the right.

Suppose that there is such a table $T$ with $n\ge 10$ columns. Let $3$ be the least represented number in row $4$. Then $1$ and $2$ combined occur at least $7$ times in row $4$. So we can select $7$ columns whose intersections with row $4$ are only $1$s and $2$s. Delete the remaining columns. The new table $4\times 7$ has the same property like the original one. Every three distinct columns in it intersect some row at three different numbers. Moreover such a row is $1$, $2$ or $3$ because row $4$ intersects the $7$ columns only at cells with $1$s and $2$s. Hence deleting row $4$ yields a $3\times 7$ table $T_1$ which is also admissible.

Apply the same reasoning to $T_1$. The two most represented numbers in row $3$ occur at least $5$ times in it, so we can reduce $T_1$ to an admissible table $3\times 5$ with no more than two different numbers in row $3$. Hence every triple of columns in it is intersected at three different numbers by row $1$ or by row $2$. Thus row $3$ can be deleted, leading to an admissible $2\times 5$ table $T_2$.

The two most represented numbers in row $2$ of $T_2$ occur at least $4$ times, so $T_2$ can be reduced to an admissible table $2\times 4$ with at most two different numbers in row $2$. Then every three of its $4$ columns must be intersected by row $1$ at three different numbers. This is impossible since $1$, $2$ or $3$ occurs twice in row $1$. The desired contradiction follows.

1	1	1	2	2	2	3	3	3
1	2	3	1	2	3	1	2	3
2	3	1	3	1	2	1	2	3
3	1	2	2	3	1	1	2	3