# Dealing Yourself Four Aces with Perfect Shuffles

I'm reading "Magical Mathematics" by Persi Diaconis and Ron Graham. In Chapter 6 they're discussing "Neat Shuffles" and state that
Any arrangement consistent with stay-stack [pairs of cards symmetric around the middle remain symmetric around the middle] is achievab;e by a sequence of in- and out-shuffles. In particular, consider again the four aces on top of a fifty-two-card deck. Earlier, we asked if there were some sequence of shuffles that stacks them for a five-handed poker game. That is, puts the aces in positions 5, 10, 15, and 20. Since there are many ways of completing these positions consistent with stay-stack, there is indeed some way to get there using in- and out-shuffles... We hasten to add that we have no idea what such a sequence is, or even what the length of the shortest possible sequence achieving this is.

This seems straightforward enough, and I'm surprised none of their undergraduates took on the challenge. (Or perhaps it is a straightfaced gibe.) Although there are 2^26 * 26! permutations satisfying stay-stack, that is only if we care about the identity of the other cards. In reality we are merely looking for a permutation that converts

`AAAAxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx`
to
`xxxxAxxxxAxxxxAxxxxAxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx`

and that space has only 270,725 possible states, which can easily be exhaustively enumerated through breadth-first search.

Here is the shortest sequence of perfect shuffles that produces the requested permutation, in 15 steps. Probably long enough to get some dirty looks at the poker table:

```    AAAAxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
in  xAxAxAxAxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
in  xxxAxxxAxxxAxxxAxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
in  xxxxxxxAxxxxxxxAxxxxxxxAxxxxxxxAxxxxxxxxxxxxxxxxxxxx
in  xxxxxxxxxxAxxxxAxxxxxxxxxxxxxxxAxxxxxxxxxxxxxxxAxxxx
in  xxxxxxxxxxAxxxxxxxxxxAxxxxxxxxxAxxxxxxxxxxAxxxxxxxxx
in  xxxxxxxxxxAxxxxxxxxxxAxxxxxxxxxxAxxxxxxxxxxAxxxxxxxx
in  xxxxxxxxxxxxAxxxxxxxxAxxxxxxxxxxxxAxxxxxxxxAxxxxxxxx
out xxxxxxxxxxxxxxxxxAxxxxxxAxxxxxxxxxxAxxxxxxAxxxxxxxxx
out xxxxxxxxxxxxxxxxxxxAxxxxxxxxxxxxxAAxxxxxxxxxxxxxAxxx
in  xxxxxxxxxxxxxxAxAxxxxxxxxxxxxxxxxxxxxxxAxxxxAxxxxxxx
in  xxxxxxxxxxxxxxxxxxxxxxxxxxAxxAxxxAxxAxxxxxxxxxxxxxxx
out xAxxxxxAxxxxxxxAxxxxxAxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
out xxAxxxxxxxxxxxAxxxxxxxxxxxxxxxAxxxxxxxxxxxAxxxxxxxxx
out xxxxAxxxxAxxxxxxxxxxxxxxxxxxAxxxxAxxxxxxxxxxxxxxxxxx
out xxxxAxxxxAxxxxAxxxxAxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx```

Of course, all that is required is that 4 of the 5 cards you receive are aces, so it turns out there is a slightly better solution that puts aces in the 5th, 15th, 20th, and 25th positions:

```xxxxAxxxxAxxxxAxxxxxxxxxAxxxxxxxxxxxxxxxxxxxxxxxxxxx -- 14 shuffles
xxxxAxxxxAxxxxxxxxxAxxxxAxxxxxxxxxxxxxxxxxxxxxxxxxxx -- 16 shuffles
xxxxAxxxxxxxxxAxxxxAxxxxAxxxxxxxxxxxxxxxxxxxxxxxxxxx -- 13 shuffles
xxxxxxxxxAxxxxAxxxxAxxxxAxxxxxxxxxxxxxxxxxxxxxxxxxxx -- 17 shuffles```

Even for the longest of these we only have to explore 102625 of the combinations, so there could be some 'hard' permutations which require close to 34 moves, or the limit could be around 18--- I could find out for sure, but I'm lazy.

Python code: http://pastebin.com/5CAVpNjm
Tags:
• Post a new comment

#### Error

default userpic