Thirty-six officers problem

The thirty-six officers problem is a mathematical puzzle proposed by Leonhard Euler in 1782.[1][2]

The problem asks if it is possible to arrange six regiments consisting of six officers each of different ranks in a 6 × 6 square so that no rank or regiment will be repeated in any row or column. Such an arrangement would form a Graeco-Latin square. Euler correctly conjectured there was no solution to this problem, and Gaston Tarry proved this in 1901,[3][4] but the problem has led to important work in combinatorics.[5]

Besides the 6 × 6 case the only other case where the equivalent problem has no solution is the 2 × 2 case, i.e. when there are four officers.

See also

References

  1. Euler, L., Recherches sur une nouvelle espece de quarres magiques (1782).
  2. P. A. MacMahon (1902). "Magic Squares and Other Problems on a Chess Board". Proceedings of the Royal Institution of Great Britain XVII: 50–63.
  3. Tarry, Gaston (1900). "Le Probléme de 36 Officiers". Compte Rendu de l'Association Française pour l'Avancement de Science Naturel (Secrétariat de l'Association) 1: 122–123.
  4. Tarry, Gaston (1901). "Le Probléme de 36 Officiers". Compte Rendu de l'Association Française pour l'Avancement de Science Naturel (Secrétariat de l'Association) 2: 170–203.
  5. van Lint, J.H.; Wilson, R.M. (1992), "Chapter 22. Orthogonal Latin squares", A Course in Combinatorics, Cambridge University Press, ISBN 0-521-42260-4

External links

This article is issued from Wikipedia - version of the Monday, January 04, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.