Previously I wrote about latin squares and set a puzzle.
Can we make a latin square where all possible pairs are represented in adjacent squares?
We can demonstrate this for an n x n latin square where n = 12
In the above images, the normalised latin square only has 12 different pairs out of a possible 66. The density plot shows the pairings in the lower triangle, grey represents 0. A randomly generated latin square (where all rows and all columns feature 1 to 12 exactly once) is shown where all possible pairs are captured. The density of pairings shows that some pairings are captured multiple times.
So, the answer is yes. But the next question is: what is the probability that a randomly generated latin square has this property?
In the last post, I optimistically stated that I would be back with the answer “next week”. Well, I managed an answer easily enough but failed to get a mathematical solution.
An answer
I generated different sized latin squares using the method described in the last post, i.e. a randomised sequence as a “seed”, then filling columns by rotation, and generating unique latin squares by permuting the columns. This is the result, consistent over several runs:
| n | Latin squares tested | All-pairs latin squares found | Fraction |
| 1 | 0 | 0 | 0 |
| 2 | 2 | 2 | 1 |
| 3 | 6 | 6 | 1 |
| 4 | 24 | 16 | 0.667 |
| 5 | 120 | 110 | 0.917 |
| 6 | 720 | 420 | 0.583 |
| 7 | 5040 | 4130 | 0.819 |
| 8 | 40320 | 20704 | 0.514 |
| 9 | 362880 | 255924 | 0.705 |
| 10 | 3628800 | 1562480 | 0.431 |
| 11 | 39916800 | 24093674 | 0.604 |
| 12 | 479001600 | 173085936 | 0.361 |
Regardless of the starting sequence, the method generates a fixed fraction of “all-pairs” latin squares vs latin squares that do not have all pairs in adjacent squares.
I couldn’t see an obvious pattern for the number of “all pairs” latin squares generated. Well, the number generated is divisible by n and by 2 (because there are twice as many squares due to reflection along the vertical axis). But this leaves nothing obvious to figure out the formula.
“Even n” latin squares and “odd n” latin squares have a different fraction of “all pairs” latin squares, and both decrease with increasing n. The decrease in fraction for both is approximately linear.
\(y = 1.18 – 0.053x\) and \(y = 0.8 – 0.038x\)
This is a solution of sorts. It says that the probability is lower than 92% for n > 3, and suggests that large n latin squares have no “all pairs” solution. OTOH, these results depend on the generation algorithm. As a next step to solving, probably computing all unique latin squares of size n and testing them for “all pairs” is the way to go. As described in the last post this gets difficult very quickly with increasing n.
If you know the answer to this problem or have an idea for a proof, let me know!
Fun fact
I was describing latin squares to a small person and they remembered this example in “Rotten Romans” by Terry Deary.
—
The post title is taken from “Latin Quarter” by Naked City. I have two versions, I’ll go for the one from “Live Vol. 1 Knitting Factory 1989”.