Navigation Menu

The Kruskal-Dynkin Count

Nov 12, 2023

Introduction

In this write-up, I’m going to talk about the Kruskal-Dynkin count, a card trick based on mathematics. I’ll give a heurisitic argument for why the trick works, and then present some experimental data about how the trick changes as the values of the cards change. It turns out that the trick works much better with some decks of cards than others.

The Trick

The Kruskal-Dynkin count is a classic. There any countless variations on how to perform it. Here is a barebones presentation of the trick: A magician explains a simple counting procedure to their audience, gives them a deck of cards, and leaves the room. The audience shuffles the deck, lays the cards in a row face-up, selects any card, then counts along the row of cards. The audience uses the value of their intial card as a number of steps to count. They repeat the counting procedure until they arrive at some final card near the end of the deck. The magician returns, and instantly plucks the audience’s final card from the table.

When this trick first appeared, magicians were baffled that such a trick was possible. The magician doesn’t have any control whatsoever. They don’t shuffle the deck. They don’t layout the cards. They aren’t even present for most of the trick. How could such a trick possibly work?

The Trick on Paper

To get a feel for the trick, let’s try it out on paper1. The deck is shuffled and laid out below. For the purposes of this trick, we only care about the values of the cards. We count $J = 11$, $Q = 12$, and $K = 13$. Here is what would happen if you started you started counting at the ${\color{red}\fbox{6}}$ in the first row.

\[\begin{array}{cccccccccc} K& 10& {\color{red}\fbox{6}}& 9& 7& 2& J& 6& {\color{red}\fbox{1}}& {\color{red}\fbox{5}}\\ 10& 5& 3& K& {\color{red}\fbox{1}}& {\color{red}\fbox{9}}& 2& 8& 4& Q\\ J& Q& 3& Q& {\color{red}\fbox{5}}& 10& K& Q& 2& {\color{red}\fbox{3}}\\ 8& 4& {\color{red}\fbox{7}}& J& 5& 8& J& 7& K& {\color{red}\fbox{9}}\\ 9& 10& 6& 4& 7& 2& 6& 4& {\color{red}\fbox{3}}& 1\\ 1& {\color{red}\fbox{8}} \end{array}\]

To put it another way, the count starting from ${\color{red}\fbox{6}}$ continues: \[ {\color{red}{\color{red}\fbox{6}} \to {\color{red}\fbox{1}} \to {\color{red}\fbox{5}} \to {\color{red}\fbox{1}} \to {\color{red}\fbox{9}} \to {\color{red}\fbox{5}} \to {\color{red}\fbox{3}} \to {\color{red}\fbox{7}} \to {\color{red}\fbox{9}} \to {\color{red}\fbox{3}} \to {\color{red}\fbox{8}} } \] Now, try the trick for yourself. Pick a card somewhere in the deck, as laid out above, and count. Wherever you start, I bet that you will arrive at the same end point ${\color{red}\fbox{8}}$2.

How It Works

The Kruskal-Dykin count works because of an observation about a special class of Markov chains. The mathemagical basis of the trick is the following: Suppose that two people are counting along the row of cards. If they ever arrive at the same card, at any point in the counting, then they will arrive at the same final card.

In keeping with mathematical tradition, we call the sequence of cards used during the counting procedure “walks”. The counts that we make during a walk will be the “steps”. We say that two walks “collide” if they contain a common card. And it turns out that, for a shuffled deck of cards, there will often be a such a “collision”. How often3? About $69\%$ of the time.

The method of performing the trick is straight forward. The audience arrives at some final card. The magician walks in, picks a card at random, and produces their own walk. It is quite likely that this path will collide with the one picked by the audience. If the walks collide, then they have have the same final destination. And so, the magician probably picks up the right final card.

Heuristic Calculation

A shuffled deck is so complicated, that we can’t give an exact probability for the trick succeeding. Instead, we give a heuristic calculation which suggests that the trick should often work. Once we’ve give the heuristic, we will do some computer simulations to see what happens for different decks of cards.

Suppose that the audience selects their initial card, and perform their walk. We’ll assume that each time they count their way to a new card, they count approximately the average $A$ of the values of the cards. For a standard deck of cards, this average is: \[ A = \frac{1 + 2 + \dots + 13}{13} = 7. \] The standard deck has $N = 52$ cards in it. Thus, their walk will have about $n = N/A$ steps in it: \[ n = \frac{52}{7} \approx 7.42. \] The magician now arrives, sees the row of cards, picks a random card, and performs a walk. We estimate the probability $P$ that the walks do not collide. Assume that each step that the magician takes has average size $A$. The magician must avoid the cards in the audience’s walk, so they must miss one card per step. This gives: \[ P = \left( \frac{A - 1}{A} \right)^n = \left( \frac{6}{7} \right)^{7.42} \approx 0.3186 \] It follows that the trick succeeds with probability $1 - P \approx 68.13\%$. That’s really close to the value $69\%$ mentioned above. Before we proceed to the computer simulations, let’s make a note of the heuristic formula we just used. The heuristic probability of a collision is: \[ \mathbb{P}(\textrm{Collision}) = 1 - \left( \frac{A - 1}{A} \right)^{N/A} \]

Computer Simulations

Now that we have this formula, let’s play with it a bit. How does the trick work for different decks? It is impossible to get exact answers, so we did a bit of computer simulation for various decks.

A simple program written in Python4 shuffled the decks and computed the statistics for us. Each deck was shuffled 10,000 times and walks were counted. The table below records the following statistics: the total number of cards $N$ and their average value $A$, the heuristic probability of collision $\mathbb{P}(\textrm{Collision})$, and the average number of collisions. The number of collisions is a function of the deck order. It counts the number of walks from the first ten cards which arrive at the same place as the walk starting from the first card. The average number of collisions is a measure of how often the trick works.

Deck $N$ $A$ $\mathbb{P}(\textrm{Collision})$ Average Collisions
Standard deck $(4,13)$ 52 7 68% 6.9671
Pollard’s modified $(4,13)$ 52 5.3846 86% 8.5297
The spelling $(4,13)$ 52 4 97% 9.5968
Monochrome SET $(9,3)$ 27 2 99% 9.9994
Standard SET $(27,3)$ 81 2 100% 10.000 (!)

Description of the Decks

Aside about The Standard SET Deck

It is very surprising that the trick always works for the Standard SET deck. This begs for some kind of explanation. There must be a combinatorial reason why all the ways converge to the same spot. Or maybe it’s just a fluke? An overzealous rounding? We tried it out with a million trials, and it worked every time. All the walks converged to the same spot.

However, it is turns out that this really is just a fluke. There really are deck orders of the standard SET deck where the trick does not work one hundred percent of the time. However, these deck orders are extremely rare. Here is an example: $$ (1,2,3,1,2,3, \dots) $$ If we start the walk at the initial card, we get: $\fbox{1} \to \fbox{2} \to \fbox{1} \to \fbox{2} \to$ etc. The walk will end on the last $2$ in the deck. However, if we start the walk at the third card, we get $\fbox{3} \to \fbox{3} \to \fbox{3} \to$ etc. The walk will end on the last $3$ in the deck. Thus, the two walks do not collide. We don’t see this deck order in the computer simulation because it is very specific. It is highly structured7 or “non-random”. One probably would not find this deck order in a million random samples.

Conclusion

After playing with the heuristic probability of a collision, and running some computer simulations, we found that the trick is much more likely to work with a SET deck.

The Kruskal-Dynkin count works somewhat like the children’s game Snakes and Ladders. To some people, the mathematics of the trick is more interesting that the trick itself. To me, it feels like mathematics at work behind the scenes has a deeper message about life, choices, and coincidences8.

References


  1. If you’re unconvinced, and you think there is some funny business going on, then I recommend trying the trick out with a physical deck of cards. If you actually do this, let me know! I would love to find out that someone tried this trick at home. ↩︎

  2. You didn’t?! Oh no – Let me guess, you started at six in the second last row. Sneaky. ↩︎

  3. We need to be a bit more precise about what we mean here. One should really say something like: “What percentage of the walks starting from the first ten cards in a shuffled deck will collide?” That doesn’t sound as punchy as “How often?” ↩︎

  4. Programming this yourself is a great exercise. ↩︎

  5. Pollard, J. M. (2000). 84.29 Kruskal’s Card Trick. The Mathematical Gazette, 84(500), 265–267. https://doi.org/10.2307/3621657 ↩︎

  6. You should go play SET! It is a great game. ↩︎

  7. We cannot resist making a connection from this sequence $(1,2,3,1,2,3,\dots)$ to juggling. The siteswap $123$ is a two-ball juggling pattern (animation). The fact that the walks proceed $\fbox{1} \to \fbox{2} \to \fbox{1} \to \fbox{2}$ and $\fbox{3} \to \fbox{3} \to \fbox{3} \to \fbox{3}$ corresponds to the fact that the two balls in this pattern have different orbits. ↩︎

  8. One philosophical observation of the trick is the following. Generally, people have the belief that when they make choices, and act on them, those choices will impact the final outcomes of their actions. The Kruskal-Dynkin count is an example of a situation where most intial choices lead to the same outcome. This feels counter-intuitive given the fairness of the setup. It turns out that, during the counting procedure, a pile of “coincidences” force most initial choices to lead to the same outcome. ↩︎

Related tags:

Navigation Menu

Thanks for reading! If you have any comments or questions about the content, please let me know. Anyone can contact me by email.