Science & Technology

# The 36 Officers Problem Once Confounded a Legendary Mathematician

Sometimes, math is most exciting not when you explore what's possible, but when you prove what's impossible. That's what Leonard Euler believed he had done in 1782 with the now-famous 36 officers problem. The problem was that he wasn't correct — not entirely. But it would take another century to prove him wrong.

## Here Comes the General

The problem seems simple enough. It goes something like this:

Imagine you're in command of an army that consists of six regiments, each containing six officers of six different ranks. Can you arrange the officers in a 6x6 square so that each row and each column of the square holds only one officer from each regiment and only one officer of each rank?

This is an example of a Latin square. That's an arrangement of items (for example, the Latin characters A, B, C, etc.) that makes it so all of the objects on any row and on any column are different. It's sort of like a more basic version of Sudoku. If you combine two squares like this (for example, one with Latin characters, one with Greek) so that the resulting square still follows the same rules, that's what you'd call a Graeco-Latin square (aka an orthogonal Latin square).

Never one to back down from a challenge, a pioneering mathematician named Leonard Euler had a go at the 36 officers problem — and realized it was impossible. "After we have put a lot of thought into finding a solution, we have to admit that such an arrangement is impossible, though we can't give a rigorous demonstration of this," he wrote in French in his paper "Recherches sur une nouvelle espèce de quarrés magiques" in 1782.

## Autant Pour Moi!

Euler never proved his conjecture, however. That was done in 1901 by the French mathematician Gaston Terry, who painstakingly wrote out all possible arrangements of the 6x6 square to show that the 36 officers problem is impossible. If you were asked to solve the problem with a 4x4 or 5x5 square, you could do it. But not with 6x6.

Still, Euler ended up being right about that. Where Euler went wrong, however, was in the next step he took: He declared that Graeco-Latin squares are impossible if the number of cells on one side of the square takes the form 4k +2 for any whole number k. The number 6 counts in this case, since 6 = 4 x 1 + 2.

It wasn't until more than a century later in 1960 that Euler's mistake was uncovered. That was when Raj Chandra Bose, Sharadchandra Shankar Shrikhande, and Ernest Tilden Parker used computers to prove that actually, the only impossible Graeco-Latin square beyond one with six sides is one with two sides. All others are possible.

Despite his misstep, Euler got something out of the deal: Today, another word for the Graeco-Latin square is the Euler square. If only we all got such rewards for our errors!