13
$\begingroup$

Michelle has a deck of 52 playing cards, stacked in a pile with their backs facing up. She takes the first 2 cards in the pile, turns them over, and places them at the bottom of the pile. She now takes the next 3 cards in the pile and, once again, turns them over, and places them at the bottom of the pile. She proceeds like this, taking each time the next prime number of cards from the top, turning them over, and placing them at the bottom of the deck. Once she has done this for all all primes up to 47 (the largest prime less than 52), she continues in the same fashion counting in turn 2, 3, 5, etc. cards from the top and placing them at the bottom of the deck.

Will the deck of cards ever have all their backs facing up again?

$\endgroup$
12
$\begingroup$

The cards will again be all face down . . .

. . . after 11700 operations. I'll just show the first 20

 0  0000000000000000000000000000000000000000000000000000
 2  0000000000000000000000000000000000000000000000000011
 3  0000000000000000000000000000000000000000000000011111
 5  0000000000000000000000000000000000000000001111111111
 7  0000000000000000000000000000000000011111111111111111
 11 0000000000000000000000001111111111111111111111111111
 13 0000000000011111111111111111111111111111111111111111
 17 1111111111111111111111111111111111100000011111111111
 19 1111111111111111000000111111111110000000000000000000
 23 1111111111000000000000000000001111110000000000000000
 29 0111111000000000000000011111111111111111110000000000
 31 1111111111100000000000000000011111111111111110000001
 37 1111111100000010000000011111111111111111100000000000
 41 0000000000000000000000000000011111111011111100000000
 43 1000000000000010000000011111111111111111111111111111
 47 1111100000000000000000000000011111111011111111111110
 2  1110000000000000000000000001111111101111111111111000
 3  0000000000000000000000001111111101111111111111000000
 5  0000000000000000000111111110111111111111100000011111
 7  0000000000001111111101111111111111000000111111111111
 11 0111111110111111111111100000011111111111111111111111
 
But if the rules are changed slightly and the cards are moved from top to bottom in the same (not reversed) sequence, it only takes $56$ operations.
 0  0000000000000000000000000000000000000000000000000000
 2  0000000000000000000000000000000000000000000000000011
 3  0000000000000000000000000000000000000000000000011111
 5  0000000000000000000000000000000000000000001111111111
 7  0000000000000000000000000000000000011111111111111111
 11 0000000000000000000000001111111111111111111111111111
 13 0000000000011111111111111111111111111111111111111111
 17 1111111111111111111111111111111111111111111111000000
 19 1111111111111111111111111110000000000000000000000000
 23 1111000000000000000000000000000000000000000000000000
 29 0000000000000000000000000001111111111111111111111111
 31 1111111111111111111111111111111111111111111111110000
 37 1111111111100000000000000000000000000000000000000000
 41 0000000000000000000000111111111111111111111111111111
 43 1111111111111111111111111111111000000000000000000000
 47 0000000000000000000000000000000000001111111111111111
 2  0000000000000000000000000000000000111111111111111111
 3  0000000000000000000000000000000111111111111111111111
 5  0000000000000000000000000011111111111111111111111111
 7  0000000000000000000111111111111111111111111111111111
 11 0000000011111111111111111111111111111111111111111111
 13 1111111111111111111111111111111111111111111111100000
 17 1111111111111111111111111111110000000000000000000000
 19 1111111111100000000000000000000000000000000000000000
 23 0000000000000000000000000000000000000000111111111111
 29 0000000000011111111111111111111111111111111111111111
 31 1111111111111111111111111111111100000000000000000000
 37 0000000000000000000000000000000000000000000000011111
 41 0000001111111111111111111111111111111111111111111111
 43 1111111111111110000000000000000000000000000000000000
 47 0000000000000000000011111111111111111111111111111111
 2  0000000000000000001111111111111111111111111111111111
 3  0000000000000001111111111111111111111111111111111111
 5  0000000000111111111111111111111111111111111111111111
 7  0001111111111111111111111111111111111111111111111111
 11 1111111111111111111111111111111111111111111100000000
 13 1111111111111111111111111111111000000000000000000000
 17 1111111111111100000000000000000000000000000000000000
 19 0000000000000000000000000000000000000000000000011111
 23 0000000000000000000000001111111111111111111111111111
 29 1111111111111111111111111111111111111111111111100000
 31 1111111111111111000000000000000000000000000000000000
 37 0000000000000000000000000000000111111111111111111111
 41 1111111111111111111111111111111111111111110000000000
 43 0000000000000000000000000000000000000000000000000001
 47 0000111111111111111111111111111111111111111111111111
 2  0011111111111111111111111111111111111111111111111111
 3  1111111111111111111111111111111111111111111111111110
 5  1111111111111111111111111111111111111111111111000000
 7  1111111111111111111111111111111111111110000000000000
 11 1111111111111111111111111111000000000000000000000000
 13 1111111111111110000000000000000000000000000000000000
 17 0000000000000000000000000000000000000000000000000011
 19 0000000000000000000000000000000111111111111111111111
 23 0000000011111111111111111111111111111111111111111111
 29 1111111111111111111111111111111000000000000000000000
 31 0000000000000000000000000000000000000000000000000000
 result = 56
 
Found by C program.

$\endgroup$
15
$\begingroup$

Answer:

Yes.

Reasoning:

Let's call the process of turning 2, then 3, then 5, etc. up to 47 cards a batch. Performing a batch induces some permutation $p$ of the 104 faces of the cards. After $n$ batches, the induced permutation is $p^n$. However, the group of permutations of 104 faces of cards is finite, so $p$ must have finite order, i.e. there must be some $N > 0$ such that $p^N$ is the identity permutation (in this particular case $N$ would be the LCM of all lengths of cycles in $p$). So after $N$ batches, not only do the cards all have their backs facing up again, but they're even in the same order as in the beginning!

Extra:

This same reasoning shows that if you perform any fixed sequence of moves repeatedly on an initially solved Rubik's cube or other non-locking twisty puzzle often enough, you will always return to the solved position.

$\endgroup$
6
$\begingroup$

Others have already got it right, but I'd like to present a more puzzle-like solution:

Going through the numbers 2-47 once produces some deck state $Y$ (some cards face-up, others face-down) from a starting deck state $X$.

Because we're given a clearly defined sequence of reversible operations, it is possible to uniquely determine $X$ given $Y$, and, of course, vice versa.

Therefore, every deck state has a unique successor, and a unique predecessor.

This allows us to imagine that every possible deck state is a snap shackle, so that the openable part (the shackle) ties the state to its successor state's permanently closed part (the ring):

enter image description here

Now, we have quite a bunch ($2^{52}$) of these shackles, and we are going to completely ignore what the actual transformation does. Instead we'll just connect the snap shackles to each other so that

  1. no ring is left without a shackle (every state has a predecessor)
  2. no shackle is left without a ring (every state has a successor)
  3. two shackles cannot connect to the same ring (the predecessor is unique)
  4. no shackle can connect to more than one ring (the successor is unique)

Since rules 3 and 4 prevent any kind of bifurcation, the only way to fulfil requirements 1 and 2 is to build one or more closed loops. This means that every single shackle has to be a part of a simple chain loop, regardless of what the actual transformation rules are.

Or coming back out of the analogy: If you repeat any transformation (in this case, going through numbers 2-47) many enough times, you are guaranteed to eventually end up in the original deck state.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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