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. Dougherty, Steven. "36 Officer Problem." Steven Dougherty's Euler Page. 4 Aug 2006.

External links