Translating a fiendishly exceptional automorphism of $S_6$ into a lay-math puzzle

Question

Foreward: This post not a puzzle in itself, but an invitation for you to show off your puzzle-making skill regarding a given topic. Although the tag description of "puzzle-creation" seems to discourage its use in this manner, a search of its posts shows a different history and user consensus, e.g. most recently here. Let me know if there's some part of this ambiguity that needs to get sorted out on the Meta site or something.

---

It's not exactly a secret that many brainteasers can be reformulated (often as part of a Eureka moment) into a precise mathematical problem. See, for example, any Lights Out-type problem, any Konigsberg bridge-type problem, any unique-up-to-symmetry counting problem solved by Burnside's lemma, any problem solvable by traditional combinatorial game theory, or even some of my own recent puzzles. I think math makes a great inspiration for new puzzles, and creating puzzles can offer unique interpretations of mathematical results.

It's a known fact that $S_6$ (group of permutations of six objects) has exactly one "exceptional" automorphism, up to relabeling of the objects. I've always found it interesting that this fact about $S_n$ is unique to $n=6$. There are plenty of problems which sneak permutation theory or group theory into riddles (an example of the first: the 100 prisoners problem. An example of the second: Rubik's puzzles, 15-piece puzzles, or insolubility thereof. Some card-shuffling problems can fall into one or the other).

What would be a good puzzle whose statement involves as little math as possible, but whose solution intimately involves this exceptional automorphism?

Answer 1

I love this question! Here is what I managed to think of. The puzzle statement uses minimal math as required. I'm less sure whether it counts as a "good" puzzle in its current state, I think it's a bit too long and convoluted. But hopefully someone more experienced in puzzle-making can take it as a starting point, or at least find some interesting idea they can use. (I also apologize in advance for my English, I'm a non-native speaker).

---

Puzzle:

A group of evil aliens have at their disposition a powerful spaceship fleet, which they use to destroy planets whenever they feel like.

The fleet consists of 100 ships in total, numbered from $1$ to $100$. It is known that the aliens use a set of connectors, filled with a very powerful but very unstable chemical substance, to power up these ships. This chemical flows through a number of cables, which join the inputs of the connector to its outputs in some specific way. The cables can't be seen from the outside, but each connector comes with a corresponding label depicting what's inside.

The circuit board of Ship $N$ uses a fixed sequence of chained $N$-cable connectors, with the $N$th overall input of the sequence connected to the $N$th respective overall output as in the picture below.

                                            

The circuit is always designed in such a way that the chemical flows in a single closed loop. This is extremely important, otherwise the resulting magnetic instability would make the ship explode.

The aliens collectively enter a deep hibernation state every night. There is a group of saboteurs whose home planet is next in line to be destroyed, and so would like to disable the alien fleet before that can happen. They plan to do this by swapping the labels of the connectors in the right way while the aliens are sleeping.

But the aliens are aware of the possibility of a sabotage: after all, they have garnered many enemies during their planet-destroying quest. As mentioned, the connectors contain an extremely unstable chemical, so they cannot be opened or tampered with at all. They can't even check the inputs one by one: the chemical must always flow through all the cables at the same time so as not to disturb the delicate equilibrium of forces. Despite these limitations, the aliens have in their possession the Connector Chain Comparing Contraption (abbreviated C4), a miracle of engineering which is able to compare any two arbitrary chains of connectors and tell whether they act the same for all possible input signals or not. This allows the aliens to make sure that the labels of the connectors are internally consistent. For example, the C4 can be used to check whether two copies of the three-cable connector labelled XI chained together act the same as a single three-cable connector labelled III; if the C4 returns a "No" answer, it is certain that at least one of these three connectors is mislabeled. To prevent the ships from being harmed, the aliens always use the C4 to meticulously test every possible pair, triplet, etc. of $N$-cable connectors (not only those who will be loaded onto the ship, but the whole supply) for inconsistencies in the labels before loading the connector chain onto Ship $N$'s circuit board.

However, the aliens know that the C4 is not powerful enough to ensure that the labels match the true content of the connectors. Long ago, there was an incident where the manufacturer sent all the connectors of Ship $57$ horizontally flipped by mistake (that manufacturer is now dead). Clearly, the C4 is unable to detect that kind of mistake. Fortunately for the aliens, such "C4-invisible" mislabelings have always turned out to be inoffensive in practice: in every known case, the mislabeled sequence of connectors still produces a circuit with a single loop when loaded onto the ship. The following image shows another example, where a former group of saboteurs managed to bypass C4 by following the strategy depicted in the upper part of the image: assign a given $4$-cable label to the connector obtained by moving the third input and output to the leftmost position (keeping the connections the same), and do this for all possible $4$-cable labels. This sabotage failed; as shown in the lower part of the image, the mislabeled chain of connectors still produced a single loop of cable, allowing Ship $4$ to function normally.

                   

After checking lots of examples by hand, the aliens have concluded that all "C4-invisible" mislabelings are most likely harmless, and consequently that their routine checks with the C4 device will suffice to prevent any possible sabotage. But are they right...?

Can the saboteurs succeed? If so, what strategy must they follow?

---

Solution:

An $N$-cable connector can be thought of as a map from the set of $N$ inputs (taken in order) to the set of $N$ outputs (taken in order). This evidently corresponds to a permutation, i.e., an element of the group $S_N$. The existence of the C4 machine forces the saboteurs to relabel these elements in such a way that composition of permutations is preserved, so a "C4-invisible" label swapping defines an automorphism of $S_N$.

If we load an arbitrary chain of connectors to Ship $N$, generically we will have $n$ loops, with respective lengths $l_1, l_2, \ldots, l_n$, such that $\sum_{i=1}^n l_i=N$. The unordered list $(l_1, l_2, \ldots, l_n)$ defines the cycle type of the permutation associated to the chain of connectors. The statement of the puzzle implies that Ship $N$ will work if and only if the circuit forms a single loop, in which case the cycle type is necessarily $(N)$. It is known that inner automorphisms of $S_N$ preserve the cycle type of its elements, so since $S_N$ has no outer automorphisms for $N\neq 6$, it is mathematically impossible for the label swapping to make Ship N malfunction if $N\neq 6$.

However, if $N=6$, it can be easily checked that the outer automorphism of $S_6$ sends permutations of cycle type $(6)$ into permutations of cycle type $(1,2,3)$, i.e., it turns the single loop into three loops of different lengths. So this is the solution of the problem: swapping the labels of all the $6$-cable connectors according to this automorphism (i.e., according to any representative in the equivalence class corresponding to the nontrivial element of $\mathrm{Out}(S_6)$) will make Ship $6$ explode and save the saboteurs' home planet.

I don't know how plausible it is that someone who isn't already familiar with group theory could stumble upon the solution, but at least the emphasis on loops of cables naturally leads one to think about cycle types, which is a crucial element of most proofs that $S_6$ is the only symmetric group with a nontrivial outer automorphism (see e.g. here).

Answer 2

I suggest we break the post down into 2 challenges:

• introduce the outer automorphism w/o any explicit reference to group theory or to modern algebra;
• find a good puzzle (emphasis by me) whose solution requires this peculiar automorphism.

This early in the year, I can only answer to the 1st: I do not expect it to be accepted, only to tickle your brains into answering the 2nd.

---

Last Xmas, I had the privilege to examine an early ms. of Rustichello's Devisement du Monde, to which were appended some folios in Latin by one Lissos Tian, who claimed to be from Kashi (Benares) &, as drogoman for European merchants, to have traveled farther than the Stone Tower. Whether he was in contact with Marco Polo himself is anyone's guess, as well as any relationship he might have with Edouard Lucas' informant. I translated the following lines from this appendix and added the [bracketed glosses]:

In these mountain inns [along the Vakhsh river], they play dice all night with great passion; the game is quite different from yours so I go into some details.

The tenens [croupier] sits at the table, before him a plate on which are 5 equally spaced slots & on each a rosace-like symbol: a besant called the Sun, a mural crown or Tower, a rope in a quintefoil knot or Noose, a six-sail Mill and a heraldic Rose.

The same are repeated on the punters' plates, although in distinct positions except for the Sun & Rose, which are as on the croupier's. Also, their plates can rotate and each of the 5 slots is filled with a token on which [before the 1st round of the game] the symbol is repeated; only the croupier is allowed to handle these tokens, with heavy fines if the punters should but touch them.

The game goes in rounds. The punters ante 2 coins to the pot, then throw 2 dibstones [5-faced dices now called Shagai] to determine the tokens to call out. If they are the same, the croupier wins half the pot, the other half hanging till next round; else, he swaps those 2 tokens on each of the punters' plates. Before he is over, the punter whose position matches the croupier's plate claims half the pot if the match is plain or the full pot if it is hidden, i. e. if the Sun is surrounded by Mill and Noose in stead of Rose and Tower. If no plate matches, the pot hangs till next round.

The croupier pays the winning punter or, if the claim be spurious as s/times happens when the beer is strong & dawn is nigh, he revokes it thus: he turns the plate to bring the Sun to match, if the Rose is to its left he reverses the tokens, if the match is hidden he swaps them 3 times in succession to bring the Rose next to the Sun. The faulty punter is fined 2 coins for a plain match, 1 for a hidden one.

---

To summarize in more modern terms: on each round the 5 punters have distinct configurations, at most one of which matches the winning one, on permanent display before the croupier; the winner must claim the pot before 2 designated tokens are swapped on his plate. The match can be plain (Fig. 1)

or hidden (Fig. 2),

in each case direct or reversed, i. e. a mirror-image of the direct match. If a punter is mistaken, the croupier reverses his config if needed i. e. swaps tokens 1-4 and 2-3 then, if the Rose is at position 2, successively swaps 1-2, then 2-4, then 4-3, exposing the mismatch.

The puzzle is to explain the following facts:

1. on each round, at most one of the 5 punters has a valid claim;
2. if a claim was revoked, the game goes on w/o need to undo the swaps that exposed the mistake;
3. the pot does not hang twice in succession by want of claim;
4. more generally, noone claims twice in succession.

I reckon it is rather a homework exercice in group theory; as I said, I did not intend it to be good, only to state it w/o group-theoretic jargon. I think its main weakness as a puzzle is, it only relies on the auto- part of the outer automorphism, to wit, its bijectivity. What makes it intriguing is the morphism part: the fact it commutes with the group law of $S_6$. I suggest elegant puzzles would require the solver to make use of this.

Of course, the exotic injective morphism $S_5 \rightarrow S_6$ is a classic; however, I am not aware it was described as embedded in a casino game anytime before; if you know better, you are welcome to comment below. For obvious reasons, Lissos Tian's travel notes have not met any publisher yet and this is not planned to change.

The ms. implicitly proves (I would deeply resent your doubting its authenticity) the rules of the game are simple enough to be explained in Turkic-Tocharian-Persian pidgin and in text-only Mediaeval Latin. Anyway, I believe they are simpler than those of Nain Jaune and variants are accessible to kindergarten graduates. Regardless of whether or not they would have fun playing it, that is.

Answer 3

You might be interested in checking out the Number Rotation Puzzle (i.e. Twiddle) described in eg. this PSE post here:

A Guide to the Number Rotation Puzzle

The relevant part starts from the section titled "Part V: Special Cases --- 3×4 board with 3×3 rotating blocks". Here is a short summary on its relation with the exceptional automorphism $f^*: S_6\cong S_6$:

Consider the group $G\le S_{12}$ generated by the two possible rotational moves of the puzzle, which directly acts on the 12 squares of the puzzle. This group must preserve the two different parities of the squares, which form 2 orbits of size-6 each. It turns out that within each single parity of 6 squares, any permutation of those 6 squares can be achieved by a unique! permutation $\sigma\in G$. Doing more bookkeeping work, we may distinctly label the 12 squares arbitrarily, and so each $\sigma\in G$ induces two separate permutations $\sigma_\text{odd}\in S_6$ and $\sigma_\text{even}\in S_6$ on the two size-6 orbits respectively which we label by "odd" and "even" for convenience. Then this mapping $f^*(\sigma_\text{odd})=\sigma_\text{even}$ is an exceptional automorphism of $S_6$. (Moreover every element $\sigma\in G$ arises this way.)

I'll leave all the other details to that post which I'm citing, where greenturtle3141 has explained the situation of the 3×4 puzzle better than I possibly can.

---

Furthermore we're also getting a free bonus group-theoretic result, in the immediately earler subsection from the post, titled "2×3 board with 2×2 rotating blocks". There greenturtle3141 cites a different post by Jaap Scherphuis, whose terminologies I'll adapt in the following explanation:

https://www.jaapsch.net/puzzles/pgl25.htm

Again consider the group $H\le S_6$ generated by the two possible rotational moves of the puzzle, and its action on the 6 squares of the puzzle. Moreover, this group $H$ also acts on the 5 different perfect matchings V,W,X,Y,Z on the 6 squares, as defined by Jaaps Scherphuis. Now it turns out that any permutation of the 5 matchings is achieved by a unique! permutation $\sigma\in H$ from the available-moves group. Again we keep track of the distinctly labeled matchings and distinctly labeled squares in the puzzle, by naming for each $\sigma\in H$, its induced permutation $\sigma_\text{pair}\in S_5$ on the 5 matchings and its induced permutation $\sigma_\text{cell}\in S_6$ of the 6 squares. Then the mapping $g^*(\sigma_\text{pair})=\sigma_\text{cell}$ is the exotic embedding $g^*:S_5\hookrightarrow S_6$. (Moreover every element $\sigma \in H$ arises this way.)

More on the exotic embedding $g^*:S_5\hookrightarrow S_6$ can be read in the Wikipedia article (which also describes how the two morphisms $f^*,g^*$ are related to each other):

https://en.wikipedia.org/wiki/Automorphisms_of_the_symmetric_and_alternating_groups#Exotic_map

Again, I leave out the rest of the details and I encourage people to read the aforecited posts which have explained these phenomena better than I possibly could.