September 2016
Motty Porat got a '*' as the only solution which proved optimality:
Dear Ponder,
Phew... This was something else!
But I'm thankful that 17 years after I learned that finite groups had interesting structures, something has finally forced me to delve into one.
Here is my solution, with only one violation, and a proof that there must be a violation.
CBACBADBCDABDCADBCDABDCA
BACDABCDABDCADBCDABDCABC
DCBADCBADCBACBDACBACDBAD
ADDBCDACBACDBACBADCBACDB
The process:
Let p[1]..p[24] be the ordering of the permutations. Since the permutations are a group, we can talk about their quotients r[1]..r[23] such that:
p[t+1] = p[t] * r[t]
p[t+2] = p[t] * r[t] * r[t+1]
In order to avoid violations, r[t], r[t+1], and r[t]*r[t+1] must be shuffles - permutations that move all elements.
There are nine shuffles, which are generated by three of them:
a = 3142 a^2 = 4321 a^3 = 2413
b = 4123 b^2 = 3412 b^3 = 2341
c = 4312 c^2 = 2143 c^3 = 3421
Notice that the order of a, b, and c is 4.
Looking at the multiplication table of the shuffles, we can see that:
- They generate the entire group of permutations.
- The products of two squares is the third one, e.g. a^2 * b^2 = c^2. (from the a,b,c above)
- Any other product of shuffles is not a shuffle, e.g. a*b = 2314; the 4 is at the 4th place.
As said, r[t], r[t+1], and r[t]*r[t+1] must be shuffles. Therefore r[t] and r[t+1] must be either:
(I) powers of the same generator, e.g. a^3 and a^2 => r[t]*r[t+1] = a^5 = a.
(II) squares, e.g. b^2 and a^2 => r[t]*r[t+1] = c^2.
- "The fundamental law of Ponder 9/16"
The series a^2, a, a^2, b^2, b, b^2, a^2, a, a^2, ... satisfies these requirements alternatively.
My solution is this series plus some improvisations at the ends. They include a violation (r[2] is not a shuffle), but luckily, both r[1]*r[2] and r[2]*r[3] are again shuffles, so the violation does not propagate to neighbors of neighbors!
The breakthrough:
Since the squares (a^2, b^2, c^2) play an important role, let's check their effect on the other elements.
Let P = all 24 permutations;
Id = the unit element = 1234;
G = {Id, a^2, b^2, c^2} = {Id, a^2, b^2, a^2*b^2} = the subgroup of the squares.
The quotient group P/G comprises 6 cosets of 4 elements. I spared you their exact values.. For each x, multiplying x by the members of G (a^2, b^2, c^2) keeps it in the same coset, of course (xG), whereas multiplying x by a, b, or c jumps to a different coset in an orderly fashion:
My solution:
A proof that there must be a violation:
Back to the "fundamental law", let's divide the series of quotients (r[1]..r[23]) to sub-sequences with the same generator, e.g. [ a^2, a, a^2 ].
Each sub-sequence is at most 3 items long*, so there are at least 8 sub-sequences, and thus 7 joint-points. The joints are two squares, e.g. r[t] = a^2, r[t+1] = b^2. But then, p[t], p[t+1], and p[t+2] are all in the same coset. There are 6 cosets, so we can't visit them 7 times (and "burn" 3 elements each time) without duplication!
* If, for example, r[1], r[2], r[3], and r[4] were powers of a, then p[1], p[2], p[3], p[4], and p[5] would be p[1] times a power of a (including a^0). But there are only four different powers of a, and therefore one will repeat.