Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  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
1  
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
add comment

1 Answer

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.