Thirty-six officers problem
From Wikipedia, the free encyclopedia
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 6 regiments consisting of 6 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] but the problem has led to important work in combinatorics.[4]
Besides the 6 by 6 case the only other case where the equivalent problem has no solution is the 2 by 2 case, i.e. when there are 4 officers.
[edit] 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. http://books.google.com/books?id=cuudxJgEnyEC&pg=PA54&dq=euler+36-officers&as_brr=1&ei=f7m_RoiIL4LIoAKHrajwBQ.
- ^ G. Terry (1900–1901). "Le Probléme de 36 Officiers". Comptes Rendu de l' Association Française pour l' Avancement de Science Naturel 1: 122–123 & 2170–2203. http://books.google.com/books?id=qzkDAAAAIAAJ&q=36+%22Recherches+sur+une+nouvelle+espece+de+quarres+magiques%22&dq=36+%22Recherches+sur+une+nouvelle+espece+de+quarres+magiques%22&ei=Y7e_Rp2cBKHgoAKI0tXvBQ&pgis=1.
- ^ Dougherty, Steven. "36 Officer Problem." Steven Dougherty's Euler Page. 4 Aug 2006.
[edit] External links
- Euler's Officer Problem at Convergence
