Mathematics behind this card trick

1. Suppose I have $21$ playing cards. I distribute them in $3$ columns and tell you to choose mentally a card. Then just indicate in which column the card is.

2. I pick up one of the columns which doesn't contain your card, then the column which contains your card then the remaining column.

3. Now I deal the cards in $3$ columns again, starting from the left to the right, and repeating the process until there are no cards left in my hand. I ask you to indicate to me in which column your card is.

4. I repeat step 2 then 3.

5. I repeat step 2.

Now by counting either way in the deck of $21$ cards, your card will be the 11th card.

I've tried using modulo to understand the problem but I'm stuck doing integer divisions. So does anyone have a simpler way to explain the trick.

Also could anyone explain why it works only for odd number of cards in each column and why it requires additional steps for more cards. e.g for $17 \cdot 3 = 51$ requires an additional step compared with $21$ cards?

EDIT: I forgot to add that the number of cards you have to count for the final step equals

$$1.5\text{ times the number of cards in each column} + 0.5$$

Solution 1:

Suppose that, when you first lay the cards on the table, the card I choose is at position $x$ in its column. You don't know $x$, but you know that $1\leq x\leq 7$.

Now, when you pick up the cards, my card will be at position $7+x$ in the full stack. The second time you lay the cards on the table, my card will appear at position $p_1=\lceil\frac{7+x}{3}\rceil$ in its column.

The second time you pick up the cards, my card will be at position $7+p_1$ in the full stack. The third time you lay the cards on the table, my card will appear at position $p_2=\lceil\frac{7+p_1}{3}\rceil$ in its column.

Finally, when you pick up the cards for the third time, my card will be at position $7+p_2$ in the full stack. Putting this all together, my card will be at position $$7+p_2=7+\left\lceil\frac{7+\lceil\frac{7+x}{3}\rceil}{3}\right\rceil$$ in the full stack. The trick is that this is equal to $11$ for all $x$ in the range $1\leq x\leq 7$.

For a proof of this last statement, as jpmc26 mentions, one can apply the identities $\lceil\frac{m+\lceil x\rceil}{n}\rceil=\lceil\frac{m+x}{n}\rceil$ and $\lceil n+x\rceil = n+\lceil x\rceil$ (for real $x$, integer $m$, and positive integer $n$) to show that $$7+\left\lceil\frac{7+\lceil\frac{7+x}{3}\rceil}{3}\right\rceil = 7+\left\lceil\frac{7+\frac{7+x}{3}}{3}\right\rceil = 7 + \left\lceil 3 + \frac{x+1}{9}\right\rceil = 10 + \left\lceil\frac{x+1}{9}\right\rceil \enspace,$$ which is clearly equal to $11$ for $1\leq x\leq 7$.

Solution 2:

You can find a full explanation of this trick and related ones at

Gergonne’s Card Trick, Positional Notation, and Radix Sort
(Mathematics Magazine, February, 2010)

http://www.maa.org/sites/default/files/Bolker-MMz-201053228.pdf

The classic trick uses $27 = 3^3$ cards. Your $21$ card version is discussed on page 48.

Solution 3:

I've wondered this for years idly, and your asking has made me think about it. Here's an answer.

After one deal-and-gather phase, your card is in the middle third of the deck, right?

When you deal out the cards again, where does that middle third end up? In the middle third (looking top-to-bottom) of the tableau.

To see this: on the first deal, pick a card, say, the 3 of hearts. Replace everything else in its column with red cards, and everything else in the other two columns with black cards. Gather and re-deal. You'll see a red "band" in the middle (top to bottom) of the new tableau.

Now you identify your card in that middle band. When you gather up the other cards, it'll once again be in the middle third of the deck, because there's one entire column-worth of cards in front of it, and one entire column-worth of cards behind it.

But you can say more than that: suppose your card was in the first column. Well, then, it was in the middle third of the first column, wasn't it? So if each column has $k$ cards, you've got $k$ cards in front of it (from one of the other piles), and another k/3 cards (from its own pile) in front of it, and the same for cards behind it. So now it's in the middle 1/9th of the pile.

And the next time it'll be in the middle 1/27 of the pile. And so on.

Now that analysis isn't QUITE right, because $k$ might not be divisible by 3. So instead of having k + k/3 cards in front of it after two deals, you have k + floor(k/3). For instance, if $k = 8$, then you'd have $8 + floor(8/3) = 8 + floor(2.66...) = 8 + 2 = 10$ cards in front of it. But aside from this minor glitch, what you get is the following:

after $p$ "passes" on a deck of $N$ cards, your card is in the middle (roughly) $(N/3^p)$ cards of the deck. When $3^p > N$, this means that your card is the middle card of the deck.