History
Orthogonal Latin squares have been known to predate Euler. As described by Donald Knuth in Volume 4A, p.3, of TAOCP, the construction of 4x4 set was published by Jacques Ozanam in 1725 (in Recreation mathematiques et physiques) as a puzzle involving playing cards. The problem was to take all aces, kings, queens and jacks from a standard deck of cards, and arrange them in a 4x4 grid such that each row and each column contained all four suits as well as one of each face value. This problem has several solutions.
A common variant of this problem was to arrange the 16 cards so that, in addition to the row and column constraints, each diagonal contains all four face values and all four suits as well. As described by Martin Gardner in Gardner's Workout, the number of distinct solutions to this problem was incorrectly estimated by Rouse Ball to be 72, and persisted many years before it was shown to be 144 by Kathleen Ollerenshaw. Each of the 144 solutions has 8 reflections and rotations, giving 1152 solutions in total. The 144x8 solutions can be categorized into the following two classes:
| Solution | Normal form |
|---|---|
| Solution #1 | A♠ K♥ Q♦ J♣ Q♣ J♦ A♥ K♠ J♥ Q♠ K♣ A♦ K♦ A♣ J♠ Q♥ |
| Solution #2 | A♠ K♥ Q♦ J♣ J♦ Q♣ K♠ A♥ K♣ A♦ J♥ Q♠ Q♥ J♠ A♣ K♦ |
For each of the two solutions, 24x24 = 576 solutions can be derived by permuting the four suits and the four face values independently. No permutation will convert the two solutions into each other.
The solution set can be seen to be complete through this proof outline:
- Without loss of generality, let us choose the card in the top left corner to be A♠.
- Now, in the second row, the first two squares can be neither ace nor spades, due to being on the same column or diagonal respectively. Therefore, one of the remaining two squares must be an ace, and the other must be a spade, since the card A♠ itself cannot be repeated.
- If we choose the cell in the second row, third column to be an ace, and propagate the constraints, we will get Solution #1 above, up to a permutation of the remaining suits and face values.
- Conversely, if we choose the (2,3) cell to be a spade, and propagate the constraints, we will get Solution #2 above, up to a permutation of the remaining suits and face values.
- Since no other possibilities exist for (2,3), the solution set is complete.
Read more about this topic: Graeco-Latin Square
Famous quotes containing the word history:
“The greatest horrors in the history of mankind are not due to the ambition of the Napoleons or the vengeance of the Agamemnons, but to the doctrinaire philosophers. The theories of the sentimentalist Rousseau inspired the integrity of the passionless Robespierre. The cold-blooded calculations of Karl Marx led to the judicial and business-like operations of the Cheka.”
—Aleister Crowley (1875–1947)
“History has neither the venerableness of antiquity, nor the freshness of the modern. It does as if it would go to the beginning of things, which natural history might with reason assume to do; but consider the Universal History, and then tell us,—when did burdock and plantain sprout first?”
—Henry David Thoreau (1817–1862)
“When the landscape buckles and jerks around, when a dust column of debris rises from the collapse of a block of buildings on bodies that could have been your own, when the staves of history fall awry and the barrel of time bursts apart, some turn to prayer, some to poetry: words in the memory, a stained book carried close to the body, the notebook scribbled by hand—a center of gravity.”
—Adrienne Rich (b. 1929)