I was on a trip during a summer break of my university years. We had a family friends’ gathering a few days before, and we played this silly but long game of fortune telling with a deck of regular playing cards. Part of the idea of the game is that we shuffle the cards and keep taking the top and bottom cards in the deck to see if their numbers matched. If they did, we added the pair to the list of cards we use to do the fortune telling, with each number representing a different question and each suit representing an answer of some sort. If the top and bottom cards didn’t match, which was too often the case, we added them to the discard pile. I wasn’t all that interested in the fortune telling part, but the discarding process kept coming back to me while I rested in my hotel room during the trip. It was difficult to collect all pairs of cards we needed, and we had to keep reusing the discard pile when we ran out. Was it possible for us to be in a loop of discarding cards and reusing the discard pile, never to find another pair of matching numbers? How many times would we go through the discard pile to complete the loop? There is our inspiration. Now we just need to define a few things to make it a problem.
Suppose we have a deck of cards numbered from 0 to n, and initially they are in numerical order in a pile from the bottom to the top like this:
0, 1, 2, 3, … n
For simplicity’s sake, let’s say the numbers are printed on both sides, and that there is no difference between the two sides. Also, when we “shuffle” using the process above, we don’t turn over any group of cards. This prevents us from changing the order of the cards in other ways. If we keep taking the top and bottom cards and adding them to the discard pile, when we run out of cards, the discard pile would look like this:
0, n, 1, n-1, 2, n-2, …
(Notice the card with the number 0 is always on the bottom, hence my choice to call it 0.)
The question is for any given natural number n, can we find out how many iterations of this shuffling process we have to go through to return to the order of the original deck?
For clarity, let’s try this for n=6
Iteration 0 (starting): 0, 1, 2, 3, 4, 5, 6
Iteration 1: 0, 6, 1, 5, 2, 4, 3
Iteration 2: 0, 3, 6, 4, 1, 2, 5
Iteration 3: 0, 5, 3, 2, 6, 1, 4
Iteration 4: 0, 4, 5, 1, 3, 6, 2
Iteration 5: 0, 2, 4, 6, 5, 3, 1
Iteration 6: 0, 1, 2, 3, 4, 5, 6
Now we are back to where we started, and it took 6 iterations.
This is the question about the length of the loop. We can also ask questions about the possibility of avoiding certain combinations of top and bottom cards. If we feel like it, we can also modify the shuffling process and ask the same questions. We would get a different problem.