(Pardon the formatting...it was a PDF originally)



a
rX
iv
:m
a
th
.P
R
/0
11
01
43
v
1

1
3
O
c
t
2
00
1
TheKruskal Count
JeffreyC. Lagarias
AT&TLabs- Research
FlorhamPark, NJ07932
EricRains
AT&TLabs- Research
FlorhamPark, NJ07932
Robert J. Vanderbei
PrincetonUniversity
Princeton, NJ08544
(October12, 2001)
Abstract
TheKruskalCountisacardtrickinventedbyMartinKruskalinwhichamagician“guesses”
acardselectedbyasubjectaccordingtoacertaincountingprocedure. Withhighprobability
themagiciancancorrectly“guess”thecard. Thesuccess of thetrickis basedonamathe-
matical principlerelatedtocouplingmodelsforMarkovchains. Thispaperanalyzesindetail
twosimplifiedvariants of thetrickandestimates theprobabilityof success. Theresultsare
comparedwithsimulationdataforseveral variantsof theactual trick.
AMSSubject Classification(2000): 60J10(Primary)91A60(Secondary)
Keywords: Markovchain, stoppingtime
1. Introduction
TheKruskal CountisacardtrickinventedbyMartinD. Kruskal (whoismostwell known
for his workonsolitons) whichis describedinFulves andGardner [5] andGardner [6],[7].
Inthis cardtrickamagician“guesses”onecardinadeckof cards whichis determinedby
asubjectusingaspecial countingprocedurethat wecall Kruskal’s countingprocedure. The
magiciancanwithhighprobabilityidentifythecorrectcard.
Thesubject shuffles adeckof cards as manytimes as helikes. He mentallychooses a
(secret)numberbetweenoneandten. Kruskal’scountingprocedurethengoesasfollows. The
subjectturnsthecardsof thedeckfaceuponeat atime, slowly, andplaces theminapile.
Asheturnsupeachcardhedecreaseshissecretnumberbyoneandhecontinuestocountthis
1
way till he reaches zero. The card just turned up at the point when the count reaches zero is
called the first key card and its value is called the first key number. Here the value of an Ace
is one, face cards are assigned the value five, and all other cards take their numerical value.
The sub ject now starts the count over, using the first key number to determine where to stop
the count at the second key card. He continues in this fashion, obtaining successive key cards
until the deck is exhausted. The last key card encountered, which we call the tapped card, is
the card to be “guessed” by the magician.
The Kruskal counting procedure for selecting the tapped card depends on the sub ject’s
secret number and the ordering of cards in the deck. The ordering is known to the magician
because the cards are turned face up, but the sub ject’s secret number is unknown. It appears
impossible for the magician to know the sub ject’s secret number. The mathematical basis of
the trick is that for most orderings of the deck most secret numbers produce the same tapped
card. For any given deck two different secret numbers produce two different sequences of key
cards, but if the two sequences ever have a key card in common, then they coincide from that
point on, and arrive at the same tapped card. The magician therefore selects his own secret
number and carries out the Kruskal counting procedure for it while the sub ject does his own
count. The magician’s “guess” is his own tapped card. The Kruskal Count trick succeeds with
high probability, but if it fails the magician must fall back on his own wits to entertain the
audience.
The problem of determining the probability of success of this trick leads to some interesting
mathematical questions. We are concerned with the ensemble success probability averaged over
all possible orderings of the deck (with the uniform distribution). Our ob jective in this paper
is to estimate ensemble success probabilities for mathematical idealizations of such counting
procedures. Then we numerically compare the ensemble success probabilities on a 52-card deck
with that of the Kruskal Count trick itself. The success probability of the trick depends in part
on the magician’s strategy for choosing his own secret number. We show that the magician
does best to always choose the first card in the deck as his first key card, i.e. to use secret
number 1.
The general mathematical problem we consider applies the Kruskal counting procedure to
a deck of N labelled cards with each card label a positive integer, in which each card has its
label drawn independently from some fixed probability distribution on the positive integers
N+. We call such distributions i.i.d. deck distributions; they are specified by the probabilities
2
{πj : j ≥ 1} of a fixed card having value j . We assume that the sub ject chooses an initial secret
number from an initial probability distribution on N+ = {1, 2, 3,

I see that it got cut off. If you are interested, I'll send you the PDF.

Zak

Ooops!! sleight of eyes...
please edit it for eyes friendly text magiczak

regards,
r1238ex

I'd rather just send the formatted PDF to anyone who is interested. It was my attempt to repost the PDF however, the file upload limit is about 100K too small. I tried to copy and paste the file.....but as you see...it was a failed effort.

Zak

The PDF file comes in at 21 pages, so you might be interested in going to a direct link. For those who are interested, try this....

http://arxiv.org/pdf/math.PR/0110143

or if you want to get it in a format other than a PDF file...

http://arxiv.org/format/math.PR/0110143

I am familiar with this but are there any effective effects that use this?