1
$\begingroup$

Start with a magnitude ordered list of the natural numbers that are less than a chosen even number greater than 0.

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

Repeatedly 'Perfect Shuffle' this list, after recording the 2nd value each time into another list, until doing so would result in the original list.

To 'Perfect Shuffle', interleaf the 1st half of a list with the 2nd.

{1, 2, 3, a, b, c} becomes {1, a, 2, b, 3, c}

The whole process is demonstrated below:

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
{0, 6, 1, 7, 2, 8, 3, 9, 4, 10, 5, 11}
{0, 3, 6, 9, 1, 4, 7, 10, 2, 5, 8, 11}
{0, 7, 3, 10, 6, 2, 9, 5, 1, 8, 4, 11}
{0, 9, 7, 5, 3, 1, 10, 8, 6, 4, 2, 11}
{0, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 11}
{0, 5, 10, 4, 9, 3, 8, 2, 7, 1, 6, 11}
{0, 8, 5, 2, 10, 7, 4, 1, 9, 6, 3, 11}
{0, 4, 8, 1, 5, 9, 2, 6, 10, 3, 7, 11}
{0, 2, 4, 6, 8, 10, 1, 3, 5, 7, 9, 11}

And the 2nd values of each, although the end result would be the same as with the 3rd, 4th, etc... values instead.

{1, 6, 3, 7, 9, 10, 5, 8, 4, 2}

Thinking of this list as being a loop, by which I mean that the element after the last element is the first element, and vice versa, the list has some remarkable properties.

Each element is all of the following:

1. The previous element multiplied by 6, mod 11.
2. The element two before, multiplied by 3, mod 11.
3. The element three before, multiplied by 7, mod 11.
...

4. Half of the previous element, provided this is a whole number.
5. The sum of the element 2 and 3 elements previous, mod 11.
...

This seems so surprising, it must have a names and uses, what are they?


Thank you Numberphile on YouTube for introducing me to the Perfect Shuffle, and perfect shuffling until reaching the original order.


edit:

An expanded, reworked and further generalised list:

S is the set described in this question, with natural numbers up to M. As S is a loop, S[-1] is the last element.

The list contains each natural number up to M, exactly once.

Each element, with value V and of position P, is all of the following:

Where M = 11:
    S[P-1]
        Multiplied by 6, mod 11.
        If even, halved.
        If odd, (V + M) / 2
    (S[P-2] + S[P-3]) mod 11.

(S[P-N] * S[N]) mod M.
This is enormously meta and for me the most remarkable part.
For example, again where M = 11:
    (S[P-2] * 3) mod 11.
    (S[P-3] * 7) mod 11.

I cannot help imagining, that in a cyclic space of 11 integers (mod 11), where real numbers are but a dream, that the best answer that is not just invalid/undefined for half of 1 is 6, and half of 5 is 8.

As if this could be applied in general, as if the purely integer answer to 5 / 2 is not to use rounding and get 3, but could instead be (5 + ∞) / 2.

$\endgroup$
1
$\begingroup$

Well spotted! You are obviously very good at pattern recognition! Here is an explanation for all your observations.


With a bit of thought you can see that the shuffle is given by the following formula. If $f(k)$ is the position occupied after the shuffle by the card which was in position $k$ before the shuffle, positions being numbered from $0$ to $11$, then $$f(k)=\begin{cases}2k&\hbox{if $0\le k\le5$}\\2k-11&\hbox{if $6\le k\le11$}. \end{cases}$$ So, after $m$ shuffles, card $k$ has moved to position $$f(f(\cdots f(k)\cdots))\ ,$$ where the number of $f$s is $m$. However, you can see directly from the formula that $$f(k)\equiv2k\pmod{11}\ ,$$ and so the position of card $k$ after $m$ shuffles is $$2^mk\pmod{11}\ .$$ Note that this is not quite true, because we should regard $0$ and $11$ as being different: however since cards $0$ and $11$ never move, this is not very important, and what I have just said is true for all other $k$.

This means that the card $k$ in position $1$ (that is, the second in your list) after $m$ shuffles is found by solving $$2^mk\equiv1\pmod{11}\ ,$$ and you can do this by multiplying both sides by $6^m$ to give $$12^mk\equiv6^m\pmod{11}\ ,$$ that is, $$k\equiv6^m\pmod{11}\ .$$ In other words, the identity of the card in position $1$ is multiplied by $6$ modulo $11$ after every shuffle, and this explains the first three features you have mentioned.


Your fourth observation is just the fact that $$k=\frac{f(k)}{2}\ ,$$ provided this is a whole number.
For your final observation, note that $6^3=216=209+7\equiv7\pmod{11}$. If you add the cards in position $1$ after $m$ and $m+1$ shuffles you get $$6^m+6^{m+1}\equiv 6^m\times7\equiv 6^{m+3}\pmod{11}\ ,$$ which is the card you get after the next shuffle but one.
Edit. I just noticed that you didn't ask for a proof, you asked for name and uses. The answer to that is "I don't know". But I hope you will find the above interesting, so I won't delete it.

$\endgroup$
  • $\begingroup$ Thank you, great answer :) $\endgroup$ – alan2here Mar 26 '15 at 0:44

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.