28
$\begingroup$
  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$$

$\endgroup$
  • $\begingroup$ If you do not have an odd number of cards in total, there is not a middle card $\endgroup$ – Henry Dec 12 '16 at 13:25
  • 2
    $\begingroup$ If you have $n$ cards and $3$ columns, you need $\log_3(n)$ steps (rounded up) to distinguish them $\endgroup$ – Henry Dec 12 '16 at 13:26
  • 1
    $\begingroup$ This related trick (and its explanation) might provide some insight $\endgroup$ – Omnomnomnom Dec 12 '16 at 13:29
  • $\begingroup$ I first learnt this card trick when I was 14. After learning some calculus, I was pleasant to realise that the fact that the card will eventually end up at the middle position is basically a consequence of the squeezing principle. $\endgroup$ – user1551 Dec 13 '16 at 9:13
  • $\begingroup$ @user1551 That seems like an overapplication of the squeezing principle. $\endgroup$ – jwg Dec 13 '16 at 10:30
21
$\begingroup$

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

$\endgroup$
  • 7
    $\begingroup$ You can use the fact that $ \left \lceil \frac{7+\lceil y \rceil}{3} \right \rceil = \left \lceil \frac{7+ y }{3} \right \rceil $ (see here) to show that the last expression is equal to $ 7 + \left \lceil 3 + \frac{x + 1}{9} \right \rceil = 10 + \left \lceil \frac{x + 1}{9} \right \rceil $, which makes the fact it's always 11 much more obvious. $\endgroup$ – jpmc26 Dec 12 '16 at 23:14
  • 1
    $\begingroup$ Good point. I just checked that it holds for x=1 and for x=7, therefore it holds for x in between due to monotonicity. Should I edit the answer to include your remark? $\endgroup$ – Evangelos Bampas Dec 13 '16 at 8:17
  • 1
    $\begingroup$ @EvangelosBampas: Yes! $\endgroup$ – Oddthinking Dec 13 '16 at 12:47
  • $\begingroup$ @EvangelosBampas Absolutely. (Thanks!) Comments are considered ephemeral/transient, and their primary purpose is for the improvement of a post. You can generally assume that useful content or clarification posted in them warrants an edit or an additional post. (In this case, I only provided some comparatively minor additions that just build on your answer and make the conclusion easier to see, so a separate post wouldn't be able to stand on its own.) $\endgroup$ – jpmc26 Dec 13 '16 at 14:13
14
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This answer comes dangerously close to "link only." $\endgroup$ – jpmc26 Dec 12 '16 at 22:51
  • $\begingroup$ I can see a total of 4 lines floating freely besides the link provided, which will definitly assure that the answer is too far from being called a link only if anything. $\endgroup$ – GingerHead Dec 13 '16 at 1:01
  • $\begingroup$ @jpmc26 I don't like link only answers either, but the relevant content in the link is too long to post - I'd essentially be pasting in most of the paper. The link is to the journal, so stable. $\endgroup$ – Ethan Bolker Dec 13 '16 at 2:06
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1, Definitely makes more sense to me than the algebra above. $\endgroup$ – user1717828 Dec 13 '16 at 1:00
5
$\begingroup$

Let's go step by step. After steps i) and ii) we already know that the chose card is in position $8,9,10,11,12,13,14$ in the pile. Then after dealing all the cards again in the given manner we know that the cards that were in the positions $8,9,10,11,12,13,14$ before dealing are now in places $3,4,5$ (actually it depends on the pile, but we can be sure that each of the mentioned cards is now at a position $3,4$ or $5$ in one of the three piles. So eventually after the second step we narrowed the choice to three cards.

After putting the cards in one pile again then we know that the chosen card will be in position $10,11,12$. And in the last deal obviously each of the cards will be in dealt in different pile, so we should be able to find out which one is the card for sure. But during the last deal the cards in positions $10,11,12$ are all in position $4$ in each of the new piles, hence after collecting all the cards, the chosen card will be in position $11$.

Eventually as you can see with each dealing we lower the number of possibilities from $n$ to $\lfloor\frac{n-1}{3}\rfloor + 1$.

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