11
$\begingroup$

The following Latin Square has an interesting property: there are 6*5=30 possible “ordered dominos” containing distinct digits, each occurring exactly once horizontally and exactly once vertically. For instance 36 (63) occurs horizontally in the top (bottom) row and no other. Also 36 (63) appears vertically in column Two (Five) and no other etc. Let us say that such a Latin Square is perfect. I can’t find any perfect Latin Squares of odd order except for the trivial case of 1x1. Similarly, I can’t find any perfect non-symmetrical Latin Squares of even order. Can you find an example of either of the above, or conversely prove that none exists? Special thanks to my friend @DmitryKamenetsky for a similar problem about painting a rectangle with K different colours.

I don’t know the answer to this puzzle, so this is a chance to prove you are one of the Awesome People 😊

enter image description here

Text version of image:

1 4 3 6 5 2

6 1 5 4 2 3

5 3 1 2 6 4

4 6 2 1 3 5

3 2 4 5 1 6

2 5 6 3 4 1

$\endgroup$
4
$\begingroup$

I don't know how to enumerate all the "perfect Latin squares", so I started off by enumerating all the possible templates: sets of rows satisfying the domino and Latin criteria. A template in itself creates a perfect Latin square if it is symmetric around either the center or the main diagonal, but it does not rule out the possibility that some permutation of rows, columns, and/or numbers creates another possibly-asymmetric perfect square, with row set and column set possibly belonging to different templates.

There are no templates for sizes 3, 5, or 7, so there are no squares of those sizes.

There is one template for sizes 2 and 4, two templates for size 6, and twelve for size 8:
enter image description here
The first eight size-8 templates are mostly identical, except for a reflection that changes the shown cells. Of interest, however, are the last four, which are diagonally symmetric instead of rotationally symmetric. (Note that my code does not force any symmetry except for that of the initial row and column.)

$\endgroup$
4
  • $\begingroup$ Your second 6x6 template is flawed. $\endgroup$ – Daniel Mathias Jul 18 '20 at 21:29
  • $\begingroup$ A (pair of) transcription errors, I guess: the fourth and fifth rows should be reverses of the third and second, respectively. $\endgroup$ – AxiomaticSystem Jul 18 '20 at 22:19
  • $\begingroup$ I don't understand what is the difference between a template and an actual latin square. $\endgroup$ – Florian F Jul 26 '20 at 14:54
  • $\begingroup$ In a template, every horizontal domino appears, but not necessarily every vertical one. $\endgroup$ – AxiomaticSystem Jul 26 '20 at 21:13
2
+50
$\begingroup$

Here are perfect latin squares of sizes 8,10,12,14 and 16 all as far as I can tell without obvious symmetries. Sorry about the formatting, at least it's copy-n-paste friendly (you wouldn't want to check them by visual inspection anyway, I assume).

ABGFDHCE BCHGEADF HAFECGBD CDAHFBEG GHEDBFAC DEBAGCFH FGDCAEHB EFCBHDGA

ABDGEIHCJF BCEHFJIDAG DEGJHBAFCI HIADBFEJGC EFHAICBGDJ JACFDHGBIE CDFIGAJEBH IJBECGFAHD GHJCAEDIFB FGIBJDCHEA

ABDHCKILFEJG BCEIDLJAGFKH DEGKFBLCIHAJ HIKCJFDGALEB CDFJEAKBHGLI LACGBJHKEDIF EFHLGCADJIBK KLBFAIGJDCHE JKAELHFICBGD FGIAHDBEKJCL IJLDKGEHBAFC GHJBIECFLKDA

ABDGKELJINFCMH BCEHLFMKJAGDNI DEGJNHAMLCIFBK GHJMCKDBAFLIEN KLNCGAHFEJBMID EFHKAIBNMDJGCL NACFJDKIHMEBLG MNBEICJHGLDAKF IJLAEMFDCHNKGB FGILBJCANEKHDM LMADHBIGFKCNJE CDFIMGNLKBHEAJ JKMBFNGEDIALHC HIKNDLECBGMJFA

ABDGKPFMEONJHCLI BCEHLAGNFPOKIDMJ DEGJNCIPHBAMKFOL GHJMAFLCKEDPNIBO KLNAEJPGOIHDBMFC PACFJOELDNMIGBKH FGILPEKBJDCOMHAN NOADHMCJBLKGEPIF MNPCGLBIAKJFDOHE HIKNBGMDLFEAOJCP EFHKODJAICBNLGPM LMOBFKAHPJIECNGD JKMPDIOFNHGCALEB CDFIMBHOGAPLJENK OPBEINDKCMLHFAJG IJLOCHNEMGFBPKDA

How they were constructed and why this method doesn't work for odd sizes:

If you replace A with 0, B with 1 etc. and for each domino as they sit in the latin squares compute the difference of left and right (top and bottom) fields modulo n, then you'll find that these differences line up perfectly, i.e. all horizontal (vertical) dominos with difference 2, say, i.e. 0:2 1:3 2:4 ... (n-1):1 sit in the same column (row) pair. The necessary and sufficicient condition for this construction to yield a perfect latin square is comparatively simple: the set of diffences over all column (row) pairs must be {1,2...n-1} so all dominos are present and all sums over linear subsets of column pairs, i.e. all pairs of neighbors contained in a connected block of columns (rows) must not be 0 modulo n otherwise in that row (column) a number occurs at least twice.

The latter criterion is also the reason we cannot apply this construction to the odd case, because the full matrix will have column (row) sum 1+2+3+...+n-1 = n(n-1)/2 which for odd n is 0 mod n. Thus no matter how the differences are arranged, the first and last number of each row (column) will be identical which is, of course, not allowed.

For even numbers up to 16 we can find arrangements of differences satisfying the criterion easily by brute force (few seconds with totally unoptimized code). At 18 the computer takes longer than my attention span. Also of note is that 1,-2,3,-4... will work but if applied to both rows and columns will create symmetries.

$\endgroup$
0
$\begingroup$

In the Latin square below you read the numbers always in pairs. When you read horizontally you start from left to right, when you read vertically you start from top to bottom.

524163

156234

645312

213546

432651

361425

I hope this satisfies your conditions.

Here is another square in response to your comment:

362154

135642

523416

614325

246531

451263

$\endgroup$
4
  • 1
    $\begingroup$ 14 occurs on the top row and on the bottom row. 13 does not occur on any row. $\endgroup$ – Jaap Scherphuis Jul 18 '20 at 5:59
  • $\begingroup$ The revised square seems to work. It also has some symmetry, which begs the question of what exactly is desired for a "non-symmetrical" example. $\endgroup$ – Brian Hopkins Jul 28 '20 at 23:52
  • $\begingroup$ @ Brian Hopkins. I added another square to my answer above. $\endgroup$ – Vassilis Parassidis Jul 29 '20 at 1:35
  • 1
    $\begingroup$ The two squares in the second revision are isomorphic under the permutation $(26534)$ in cycle notation, i.e., $1 \mapsto 1$, $2 \mapsto 6$, $3 \mapsto 4$, $4 \mapsto 2$, $5 \mapsto 3$, $6 \mapsto 5$. $\endgroup$ – Brian Hopkins Jul 29 '20 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.