# Does every Latin square contain a diagonal in which no symbol appears thrice?

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 twice.

Problem: Prove the above theorem.

This is quite a fun problem to solve, but there is a trap.

-
I'm pretty sure your definition of a diagonal isn't standard. When I was studying Latin squares 15 years ago, they all had two diagonals. – TonyK Nov 20 '10 at 22:52
I think what you are calling "diagonals" are transversals (this might be interesting, but OT: en.wikipedia.org/wiki/… ). – trutheality Nov 20 '10 at 23:33
At Monash, we typically use "transversal" to mean a diagonal (as defined above) with no repeated symbols. A common alternative is "transversal" instead of "diagonal" and "Latin transversal" instead of "transversal". – Douglas S. Stones Nov 20 '10 at 23:45

You can do better- Cameron and Wanless showed that every latin square possesses a diagonal in which no symbol appears more than twice.

We also show that every Latin square contains a set of entries which meets each row and column exactly once while using no symbol more than twice.

For the paper, see Covering radius for sets of permutations

-
How is this "better"? "no symbol appears more than twice" is the same thing as "no symbol appears thrice or more", isn't it? – Gerry Myerson Jul 27 '12 at 4:50