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.
In 1959, R. C. Bose and S. S. Shrikhande constructed some counterexamples (dubbed the Euler spoilers) of order 22 using mathematical insights.[6] Then E. T. Parker found a counterexample of order 10 using a one-hour computer search on a UNIVAC 1206 Military Computer while working at the UNIVAC division of Remington Rand (this was one of the earliest combinatorics problems solved on a digital computer).
In April 1959, Parker, Bose, and Shrikhande presented their paper showing Euler's conjecture to be false for all n ≥ 10. Thus, Graeco-Latin squares exist for all orders n ≥ 3 except n = 6.[7]
See also
- 36 cube
References
- ↑ Euler, L., Recherches sur une nouvelle espece de quarres magiques (1782).
- ↑ P. A. MacMahon (1902). "Magic Squares and Other Problems on a Chess Board". Proceedings of the Royal Institution of Great Britain XVII: 50–63. https://books.google.com/books?id=cuudxJgEnyEC&pg=PA54&dq=euler+36-officers.
- ↑ Tarry, Gaston (1900). "Le Probléme de 36 Officiers". Compte Rendu de l'Association Française pour l'Avancement des Sciences (Secrétariat de l'Association) 1: 122–123.
- ↑ Tarry, Gaston (1901). "Le Probléme de 36 Officiers". Compte Rendu de l'Association Française pour l'Avancement des Sciences (Secrétariat de l'Association) 2: 170–203.
- ↑ 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
- ↑ Bose, R. C.; Shrikhande, S. S. (1959), "On the falsity of Euler's conjecture about the non-existence of two orthogonal Latin squares of order 4t + 2", Proceedings of the National Academy of Sciences USA 45: 734–737.
- ↑ Bose, R. C.; Shrikhande, S. S.; Parker, E. T. (1960), "Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler's conjecture", Canadian Journal of Mathematics 12: 189–203, doi:10.4153/CJM-1960-016-5
External links
- Leonhard Euler's Puzzle of the 36 Officiers AMS featured column archive (Latin Squares in Practice and Theory II)
- Weisstein, Eric W.. "36 Officer Problem". http://mathworld.wolfram.com/36OfficerProblem.html.
 |
