A diagonal of a Latin square is a selection of n entries in which no two entries occur in the same row or column. For example: the entries marked with an asterisk below form a diagonal.
1 2* 3 4
2 3 4 1*
3 4 1* 2
4* 1 2 3
Theorem: Every Latin square contains a diagonal in which no symbol appears thrice (or more).
The asterisked diagonal in the above example is a diagonal in which no symbol appears thrice.
Problem: Prove the above theorem.
This is quite a fun problem to solve, but there is a trap.