# A Card Counting Trick

I used to call this thing a “game” but my friend Kevin (who is not the same Kevin as last week but who is also a mathematician) kept telling me it’s really more of a “trick.” So, it’s a trick, in the canon, I guess.

I was interning at a finance firm where we (the interns) were asked to “teach everyone something.” I didn’t participate (I didn’t then have the unjustified confidence that would eventually grant me the power to broadcast ramblings to a hundred and twenty thousand subscribers) BUT I did learn many fun things at that one presentation. One such thing I learned was the following game:

Deal out the cards of a 52-card deck one at a time at some set speed, except for the last one. Whoever can guess what the last one after having seen all the other cards wins.

This game was presented as a funny, minimal idea of what a “game” could be and to my recollection nobody discussed it or any strategy for it afterwards. A friend and I got very into it.

The most obvious idea is probably to just remember every card you’ve seen. I suppose maybe if you are very good at memory sports you could actually do it this way, but for my feeble mind there are easier ways.

One slightly more sophisticated strategy is to assign each card a value from 0 to 51 and note that the sum of the entire deck is 1326. Then as you flip cards you can add up the numbers corresponding to the cards you see, subtract the result from 1326, and the result will be the missing card. We can see this algebraically to convince ourselves this idea works:

```
card 1 + … + card 51 + card 52 = 1326
=>
card 52 = 1326 - (card 1 + … + card 51)
```

This idea totally works. But! You have to figure out the mapping between each card and the related number on the fly, which is at least a little tricky. And it doesn’t generalize to larger decks of cards very easily since you have to keep adding up larger and larger numbers. And it’s just not that *satisfying* as a trick!

An observation you might have shortly after coming up with this strategy is that you don’t actually need to store the *whole* value. Since every card, 0 through 51, has a unique value modulo 52, we can actually just do the entire calculation mod 52. The entire deck is 26 mod 52, so we can do algebra again:

```
card 1 + … + card 51 + card 52 = 26
=>
card 52 = 26 - (card 1 + … + card 51)
```

This seems a little better morally, at least, since we now only need log_2(52) bits of memory, which must be optimal, since we need to be able to make at least 52 different determinations by the end of the whole endeavour to point at what card we’ve got.

To be slightly more abstract, we’re tracking an object, `state`

, and each time we see a card, we update `state`

to be `state + card`

. At the end, we subtract `state`

from the sum of the entire deck to determine the missing card.

```
let state = Zero
for card in deck:
state += card
return Sum - state
```

This is still kind of tricky to do in your head, though. Addition mod 52 is not particularly easy and we still have to map each card to a unique number mod 52.

We can simplify the problem further by decomposing each card into its suit and rank and tracking each of those separately. That is, instead of a number from 0 to 51, store one from 0 to 3 to track the suit and store a different one from 0 to 12 to track the rank.

```
let state = (Suit::zero, Rank::zero);
let suit = Suit::zero;
let rank = Rank::zero;
for card in deck:
suit += card.suit;
rank += card.rank;
```

This is a bit easier! You don’t even really need to think of the suits as numbers themselves, you can just map the suits onto the numbers:

```
♦️=0
♠️=1
♥️=2
♣️=3
```

And then memorize the addition table:

And do the same for rank. Rank is still sort of hard, but you can do tricks like thinking of Queen as -1 instead of 12, and Jack as -2 instead of 11.

This is okay! But there’s still an improvement we can do. We don’t *have* to use addition mod k as our state. The thing that’s important is that our state forms an Abelian Group. If that doesn't mean anything to you, you can ignore it, but the important thing is that there is actually *another* four element Abelian Group. Here is its addition table:

I claim this is *much* better for tracking in your head. It might not look like it from the addition table, but let's look at its Cayley Graph (you can think of this as a sort of finite state machine diagram):

there’s the zero, Diamonds, which always does nothing, then every non-Diamond can be described in the same way: it’s its own inverse, and when added to another non-Diamond it gives the remaining non-Diamond.

I don’t have a good trick for tracking the rank, I think you just have to practice addition mod 13, or work in addition mod 20, or something.

Anyway, this is also a fun team activity (dare I say a "game"): set aside the last card and have each person take part of the deck, then have each person announce the sum of their portion and see if you derived the last card correctly.

This was...not database related. But talking about applying mathematical ideas to things that don't have obvious mathematical tools is part of the vibe of NULL BITMAP, and I was thinking about this recently, so I hope you enjoyed it.