Expert: Paul Klarreich - 8/21/2009

Question
We have received an assignment on card riffling in Grade 11 maths C. We are asked, among other things, to explain why a deck of even numbered cards must always go back to their original order eventually. The way we have to riffle them is by splitting the deck in half and placing one card from the bottom of each halve so that if that the original order was A ,2,3,4,5,6,7,8,9,10 - after 1 riffle the new order will be A,6,2,7,3,8,4,9,5,10.       

My theory for why the cards must always return to their original order is giving me a little grief . When riffled, the cards are going through 2 cycles however the only reason these 2 cycles return each card to its original position at the same time is because the cards are moving 2^r mod (n-1).As the number of cards (n) is always even the modulo must always be odd.

I have come up with an equation to prove this, however I'm not sure how to rearrange and solve for x.
1 = 2^x mod (2k +1)
where k is any natural number,
therefore (2k+1) is any odd number.

Is there any way, by number theory (or any method really), to prove that x must be equal to more than one value (one of which always has to be 0.)

Thank you in advance for taking the time to read my question.


Answer
Questioner: Iulia
Country: Australia
Category: Advanced Math
Private: No
Subject: Modulo problem
Question: We have received an assignment on card riffling in Grade 11 maths C. We are asked to explain why a deck of even numbered cards must always go back to their original order eventually. The way we have to riffle them is by splitting the deck in half and placing one card from the bottom of each half so that if that the original order was, say A,2,3,4,5,6,7,8,9,10 - after 1 riffle the new order will be A,6,2,7,3,8,4,9,5,10.       

My theory for why the cards must always return to their original order is giving me a little grief . When riffled, the cards are going through 2 cycles however the only reason these 2 cycles return each card to its original position at the same time is because the cards are moving 2^r mod (n-1).As the number of cards (n) is always even the modulo must always be odd.

I have come up with an equation to prove this, however I'm not sure how to rearrange and solve for x.
1 = 2^x mod (2k +1)
where k is any natural number,
therefore (2k+1) is any odd number.

Is there any way, by number theory (or any method really), to prove that x must be equal to more than one value (one of which always has to be 0.)

Thank you in advance for taking the time to read my question.
...................................................
I don't see this as a problem in number theory; it seems more like group theory.
I am not sure yet of all the details, but here is a start:

This shuffle, er... riffle, is a permutation.  Call it P.  If you do it a second time, you have a second permutation of the original order, calleds P^2.  If there are 8 cards in the deck, (remember that the first and last never move) then there are at most 8! [ that is  8-factorial] different permutations.

COMMENTS:
1. The '8' here is arbitrary; the discussion below does not depend on the '8'.
2. The number of cards in the deck does not have to be even.
3. The riffle method may be any method, as long as it is identical from one riffle to the next.  It does not have to leave any cards unmoved.

Therefore, if we do N = 8! riffles, we must have N + 1 orderings of the cards that have come up.
Therefore, if we do N = (k-2)! riffles, we must have N + 1 orderings of the cards that have come up.

Therefore, among those, there must be two that are the same.  Suppose, then, that P^A and P^B are the same.  Then if C = B-A, the rifflings:

P^A P^C = P^B

P, P^2, P^3,... ,P^C  form a (cyclic) group:

P^C is the identity.
P^(C-j) is the inverse for any P^j

P^A P^C = P^B, and so P^C is an identity element.  Then  P^C, applied to any original ordering, leaves it unchanged.

(This seems Ok, but I will think about it some more.)