Thirty-six officers problem
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, but the problem has led to important work in combinatorics.
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. 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.
- 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.
- 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, MR 0122729