7
$\begingroup$

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.

  • 1
    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.2010-11-20
  • 1
    I think what you are calling "diagonals" are transversals (this might be interesting, but OT: http://en.wikipedia.org/wiki/Problems_in_Latin_squares#Bounds_on_maximal_number_of_transversals_in_a_Latin_square ).2010-11-20
  • 2
    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".2010-11-20

1 Answers 1