Hosted by The Math Forum

Problem of the Week 930

The Shuffling Machine

_____________________________________________
MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW
_____________________________________________

Suppose that you have a card shuffling machine that takes the cards 1, 2, 3, ..., 52 and outputs them in the order 1, 27, 2, 28, 3, 29, ..., 26, 52. If we repeatedly take the cards out and put them back into the machine, then after 8 steps the cards will be back in their original order (and this is the first time they are back in order). If the machine shuffles them to 27, 1, 28, 2, 29, 3, ..., 52, 26, then it takes 52 shuffles to return to the original order.

Now, suppose we can make a machine corresponding to any permutation of the cards. What machine will take the longest to return the cards to their original order?

Source: It is well-known and possibly in S. Brent Morris' book Magic Tricks Card Shuffling and Dynamic Computer Memories (I don't have a copy).

font size="-1"> © Copyright 2001 Stan Wagon. Reproduced with permission.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.

1 Mar 2001