Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

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: code, permutations, poker, programming, puzzles
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 3 comments