This year at a holiday party Alex and I were at, a magician was making his way amongst the tables and performing some sleight-of-hand illusions as well as some classic mathematical card tricks. This afternoon, this video popped up in my Twitter feed:

Being almost done with finals for the semester I thought I’d take a few seconds and figure out how the trick works as a short exercise in reasoning.

First, some intuition: the trick works every time provided you follow the algorithm given. Therefore the three ‘chosen’ cards must be in the same place in the deck every time. This suggest the ‘cutting’ routine is for illusion only. The second half of the trick involves sequentially cards in odd ‘positions’ in the deck which suggests some relative primality.

Next, we prove to ourselves that the position of the chosen cards in the deck is deterministic. At the beginning we have four piles with sizes as follows:

We then add in the cards and cut the piles accordingly:

So, after we combine the four piles, but before we move four cards from the top to the bottom of the pile, we can tell by simplifying that the sequence of cards from bottom to top is:

If we count from the top to the bottom, after we have moved four cards from top to bottom, the three chosen cards will always be in positions 6, 22, and 38.

Now that we know what happens in the first half of the trick, we move onto the second part. It’s quite clear that the performer starts removing odd-positioned cards from the deck. So we need to show that positions 6, 22 and 38 have some special property that keeps them in the deck to the point where there are only three remaining cards. At first glance this seems unlikely. They are all even, to be sure, so they will pass the first round, but on second round, position 6 will be in position 3, so that card will get eliminated. Looking naïvely, there are of course positions that will survive four rounds of elimination, which are 16, 32, and 48, multiples of 2^4 or 16. These cards don’t occupy those positions.

It took me a moment to figure out what was going on here. Keeping the non-eliminated cards *face down* has the effect of reversing the deck, so the first card to be ‘kept’ will actually be in position 26 in the next round. When I worked the problem through a couple of times I dealt the cards to myself face-up to try and suss out which positions the chosen cards end up in. Of course, this breaks the trick completely.

Before the first pass, the chosen cards are in the following positions, and there are 52 cards in the deck.

After one round of elimination, with 26 cards in the deck

After two, with 13

After three with 6:

Finally after four eliminations and with three cards left:

Finally, then, the position *p* of a card after *n* rounds is given recursively by:

So that’s it. No magic, just some arithmetic.

this can be a very helpful web site!

FIFA 16 Ultimate Team Coins http://fifa16coinsfut.hatenablog.com/entry/2015/09/04/121932