Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The original question is posted on SPOJ, and included below:

Here is an algorithm for shuffling N cards:

1) The cards are divided into K equal piles, where K is a factor of N.

2) The bottom N / K cards belong to pile 1 in the same order (so the bottom card of the .initial pile is the bottom card of pile 1).

3) The next N / K cards from the bottom belong to pile 2, and so on.

4) Now the top card of the shuffled pile is the top card of pile 1. The next card is the top card of pile 2,..., the Kth card of the shuffled pile is the top card of pile K. Then (K + 1)th card is the card which is now at the top of pile 1, the (K + 2)nd is the card which is now at the top of pile 2 and so on.

For example, if N = 6 and K = 3, the order of a deck of cards "ABCDEF" (top to bottom) when shuffled once would change to "ECAFDB".

Given N and K, what is the least number of shuffles needed after which the pile is restored to its original order?

What I am looking for is a mathematical equation to get the answer. I simulated and observed that a card $x$ will have the new position as given by $x = (x \% k)\cdot k + k - 1 - x/k$. We start with $x=0$. In every iteration we get new value of $x$. Once $x$ is $0$ again, we are in the original configuration. So the answer is the number of iterations.

Is there a better and faster way to do it?

share|cite|improve this question
Hint: how fast you could calculate the cycles of the permutation (i.e. lengths of all of them)? – dtldarek Mar 12 '12 at 10:08
i am a noob in math. could you please point to materials i must learn in order to get the answer? – John Smith Mar 12 '12 at 11:34
The best would be "Concrete mathematics" by Graham, Knuth and Patashnik, but that one may be hard for you (still it is quite easy to obtain both from libraries or the net, so take a try). For this problem it would be easiest for you to read this and this Wikipedia's entries. – dtldarek Mar 12 '12 at 17:30

Follow each card through a number of shuffles until it returns to where it started. Keep track of the number of shuffles it takes for each card. The whole deck will return in the least common multiple of the cycle times for the cards.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.