The Magic Café
Username:
Password:
[ Lost Password ]
  [ Forgot Username ]
The Magic Cafe Forum Index » » Magical equations » » Kruskal count (0 Likes) Printer Friendly Version

magiczak
View Profile
Regular user
Granada Hills, CA
159 Posts

Profile of magiczak
(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,
**Zak**
magiczak
View Profile
Regular user
Granada Hills, CA
159 Posts

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

Zak
**Zak**
r1238ex
View Profile
Regular user
102 Posts

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

regards,
r1238ex
magiczak
View Profile
Regular user
Granada Hills, CA
159 Posts

Profile of magiczak
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
**Zak**
McCritical
View Profile
Regular user
156 Posts

Profile of McCritical
Quote:
The Kruskal Count is a card trick invented by Martin J. Kruskal in which a magician "guesses" a card selected by a subject according to a certain counting procedure. With high probability the magician can correctly "guess" the card. The success of the trick is based on a mathematical principle related to coupling methods for Markov chains. This paper analyzes in detail two simplified variants of the trick and estimates the probability of success. The model predictions are compared with simulation data for several variants of the actual trick.


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
Paradise
View Profile
Elite user
sheffieldEngland
416 Posts

Profile of Paradise
I am familiar with this but are there any effective effects that use this?
The Magic Cafe Forum Index » » Magical equations » » Kruskal count (0 Likes)
[ Top of Page ]
All content & postings Copyright © 2001-2021 Steve Brooks. All Rights Reserved.
This page was created in 0.38 seconds requiring 5 database queries.
The views and comments expressed on The Magic Café
are not necessarily those of The Magic Café, Steve Brooks, or Steve Brooks Magic.
> Privacy Statement <

ROTFL Billions and billions served! ROTFL