IBM Research | Ponder This | September 2016 solutions
Skip to main content

September 2016

<<August September October>>

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.


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:

  1. They generate the entire group of permutations.
  2. The products of two squares is the third one, e.g. a^2 * b^2 = c^2.  (from the a,b,c above)
  3. 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.