5
$\begingroup$

I was just thinking about this.

Let's say that we have a card deck with 54 cards and the $n$th card from the top is flipped. We repeat a short process of cutting the deck directly in the middle and then interleaving the cards from each pile (in other words, a perfect shuffle).

For example, if the cards were numbered from 1 to 54 from top to bottom, after interleaving the cards, the top of the deck would look like: 28, 1, 29, 2, 30, 3, ...

We repeat this process until we cut the deck in half and find the flipped card where we cut.

Is there a function of the position of the flipped card from the top ($f(n)$) for how many times you have to do this before you find the flipped card upon cutting it?

$\endgroup$
  • 3
    $\begingroup$ I'm far from the sharpest puzzler here, so take this with a grain of salt, but I hit two challenges reading this: 1) I can't totally follow the setup here. I got lost in your number examples in the middle. 2) I think your actual question will work better if you're clearer about what you're asking, "Can you produce a function that will define the exact (or minimum?) number of cuts that will reveal the flipped card?" $\endgroup$ – Jaydles May 19 '14 at 15:50
  • $\begingroup$ I know what he's talking about - it's a problem called the perfect shuffle problem. For 52 cards, 8 perfect shuffles will return the deck to its original order. $\endgroup$ – Joe Z. May 19 '14 at 18:12
  • $\begingroup$ @Jaydles Exact function $\endgroup$ – awesomepi May 19 '14 at 18:24
  • $\begingroup$ @JoeZ. That's not actually what I'm talking about $\endgroup$ – awesomepi May 19 '14 at 18:25
  • 1
    $\begingroup$ Hm, jokers. I suppose, I don't really consider them part of a standard deck, since I never play games that use them. $\endgroup$ – Kevin May 19 '14 at 22:02
8
$\begingroup$

This is a problem in group theory. You are trying to find out how many times you can apply a specific permutation to a deck of $54$ cards (in this case, the permutation is equivalent to a perfect shuffle) until a card that was originally $n$th from the top turns up $28$th from the top (which is where you would "find the flipped card if the deck were cut exactly in half").


Firstly, let's take a look at what the permutation is like. In the permutation specified in your question, you take a deck of cards arranged like this:

1 2 3 4 5 6 ... 51 52 53 54

cut it into two piles of 27 cards each, and interleave the cards so that they end up like this:

28 1 29 2 30 3 31 4 32 5 ... 53 26 54 27

This provides a function $f : [1..54] \rightarrow [1..54]$ where each number $x$ is mapped to a different $f(x)$, which is known as a bijection or a permutation. The same principle from the prisoners'-names-in-boxes problem applies, in which a permutation is a set of disjoint cycles. All it remains to do is to figure out what cycles the cards go through.

The full table of values that each number maps to are as follows:

   x: 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18
f(x): 28 01 29 02 30 03 31 04 32 05 33 06 34 07 35 08 36 09

   x: 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
f(x): 37 10 38 11 39 12 40 13 41 14 42 15 43 16 44 17 45 18

   x: 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
f(x): 46 19 47 20 48 21 49 22 50 23 51 24 52 25 53 26 54 27

And by repeatedly taking the $f$ of each number, we can figure out the cycles that result:

cycle 1: 14 07 31 43 49 52 26 13 34 17 36 18 09 32 16 08 04 02 01 28
cycle 2: 46 23 39 47 51 53 54 27 41 48 24 12 06 03 29 42 21 38 19 37
cycle 3: 05 30 15 35 45 50 25 40 20 10
cycle 4: 11 33 44 22

There are 20 numbers in the same cycle with $28$ (the positions mentioned in the first line), so if the flipped card is $n$th on top where $n$ is some number in that first row of numbers, it'll take as many shuffles to get that card 28th from the top as the distance in numbers from $n$ to $28$ going forward in the cycle.

For example, if the card is $31$st from the top, it will take 17 shuffles to get the card to 28th from the top, because $31$ is 17 spaces to the left of $28$ in that table.

But consequently, if the number is some $n$ in the other three cycles, then it will never end up 28th from the top, and you will never get it to show up when you cut the deck in half.

$\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.