Kruskal Count on:
[Wikipedia]
[Google]
[Amazon]
The Kruskal count (also known as Kruskal's principle, Dynkin–Kruskal count, Dynkin's counting trick, Dynkin's card trick, coupling card trick or shift coupling) is a
The trick is performed with cards, but is more a magical-looking effect than a conventional magic trick. The magician has no access to the cards, which are manipulated by members of the audience. Thus
(NB. This is a translation of the first Russian edition published as
by GTTI () in March 1952 as Number 6 in ''Library of the Mathematics Circle'' (). It is based on seminars held at the School Mathematics Circle in 1945/1946 and 1946/1947 at
(xii+365+1 pages); (viii+274+2 pages) (NB. This was originally published in Russian as "Markovskie prot︠s︡essy" () by Fizmatgiz () in 1963 and translated to English with the assistance of the author.) * (x+237 pages) (NB. This is a corrected translation of the first Russian edition published as "" by Nauka Press () in 1967 as part of a series on ''Probability Theory and Mathematical Statistics'' () with the assistance of the authors. It is based on lectures held at the
(2 pages) * (10 pages) * (18 pages) * (23 pages) *
https://web.archive.org/web/20221130232206/https://www.qualitydigest.com/inside/lean-column/pdca-and-roads-rome-061416.html] * * (1+xvii+1+152 pages) * (13 pages) * (17 pages) (NB. This source does not mention Dynkin or Kruskal specifically.)
probabilistic
Probability is a branch of mathematics and statistics concerning events and numerical descriptions of how likely they are to occur. The probability of an event is a number between 0 and 1; the larger the probability, the more likely an e ...
concept originally demonstrated by the Russian mathematician Evgenii Borisovich Dynkin in the 1950s or 1960s discussing coupling
A coupling is a device used to connect two shafts together at their ends for the purpose of transmitting power. The primary purpose of couplings is to join two pieces of rotating equipment while permitting some degree of misalignment or end mo ...
effects and rediscovered as a card trick
Card manipulation, commonly known as card magic, is the branch of Magic (illusion), magic that deals with creating effects using sleight of hand techniques involving playing cards. Card manipulation is often used in magical performances, especia ...
by the American mathematician Martin David Kruskal
Martin David Kruskal (; September 28, 1925 – December 26, 2006) was an American mathematician and physicist. He made fundamental contributions in many areas of mathematics and science, ranging from plasma physics to general relativity and ...
in the early 1970s as a side-product while working on another problem. It was published by Kruskal's friend Martin Gardner
Martin Gardner (October 21, 1914May 22, 2010) was an American popular mathematics and popular science writer with interests also encompassing magic, scientific skepticism, micromagic, philosophy, religion, and literatureespecially the writin ...
and magician Karl Fulves in 1975. This is related to a similar trick published by magician Alexander F. Kraus in 1957 as ''Sum total'' and later called ''Kraus principle''.
Besides uses as a card trick, the underlying phenomenon has applications in cryptography
Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
, code breaking, software tamper protection, code self-synchronization, control-flow resynchronization, design of variable-length code
In coding theory, a variable-length code is a code which maps source symbols to a ''variable'' number of bits. The equivalent concept in computer science is '' bit string''.
Variable-length codes can allow sources to be compressed and decompr ...
s and variable-length instruction set
In computer science, an instruction set architecture (ISA) is an abstract model that generally defines how software controls the CPU in a computer or a family of computers. A device or program that executes instructions described by that ISA, ...
s, web navigation
Web navigation refers to the process of navigating a network of information resources in the World Wide Web, which is organized as hypertext or hypermedia. The user interface that is used to do so is called a web browser.
A central theme in w ...
, object alignment, and others.
Card trick
The trick is performed with cards, but is more a magical-looking effect than a conventional magic trick. The magician has no access to the cards, which are manipulated by members of the audience. Thus sleight of hand
Sleight of hand (also known as prestidigitation or ''legerdemain'' () comprises fine motor skills used by performing artists in different art forms to entertain or manipulate. It is closely associated with close-up magic, card magic, card fl ...
is not possible. Rather the effect is based on the mathematical fact that the output of a Markov chain
In probability theory and statistics, a Markov chain or Markov process is a stochastic process describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally ...
, under certain conditions, is typically independent of the input. A simplified version using the hands of a clock performed by David Copperfield
''David Copperfield''Dickens invented over 14 variations of the title for this work; see is a novel by English author Charles Dickens, narrated by the eponymous David Copperfield, detailing his adventures in his journey from infancy to matur ...
is as follows.http://popularmechanics.com/science/a31136091/math-magic-trick/ A volunteer picks a number from one to twelve and does not reveal it to the magician. The volunteer is instructed to start from 12 on the clock and move clockwise by a number of spaces equal to the number of letters that the chosen number has when spelled out. This is then repeated, moving by the number of letters in the new number. The output after three or more moves does not depend on the initially chosen number and therefore the magician can predict it.
See also
* Coupling (probability) *Discrete logarithm
In mathematics, for given real numbers a and b, the logarithm \log_b(a) is a number x such that b^x=a. Analogously, in any group G, powers b^k can be defined for all integers k, and the discrete logarithm \log_b(a) is an integer k such that b^k=a ...
* Equifinality
* Ergodic theory
Ergodic theory is a branch of mathematics that studies statistical properties of deterministic dynamical systems; it is the study of ergodicity. In this context, "statistical properties" refers to properties which are expressed through the behav ...
* Geometric distribution
In probability theory and statistics, the geometric distribution is either one of two discrete probability distributions:
* The probability distribution of the number X of Bernoulli trials needed to get one success, supported on \mathbb = \;
* T ...
* Overlapping instructions
In computer programming, machine code is computer code consisting of machine language instructions, which are used to control a computer's central processing unit (CPU). For conventional binary computers, machine code is the binaryOn nonb ...
* Pollard's kangaroo algorithm
* Random walk
In mathematics, a random walk, sometimes known as a drunkard's walk, is a stochastic process that describes a path that consists of a succession of random steps on some Space (mathematics), mathematical space.
An elementary example of a rand ...
* Self-synchronizing code
In coding theory, especially in telecommunications, a self-synchronizing code is a uniquely decodable code in which the symbol stream formed by a portion of one code word, or by the overlapped portion of any two adjacent code words, is not a ...
Notes
References
Further reading
* (1+9+80+9+1 pages(NB. This is a translation of the first Russian edition published as
by GTTI () in March 1952 as Number 6 in ''Library of the Mathematics Circle'' (). It is based on seminars held at the School Mathematics Circle in 1945/1946 and 1946/1947 at
Moscow State University
Moscow State University (MSU), officially M. V. Lomonosov Moscow State University,. is a public university, public research university in Moscow, Russia. The university includes 15 research institutes, 43 faculties, more than 300 departments, a ...
.)
*(xii+365+1 pages); (viii+274+2 pages) (NB. This was originally published in Russian as "Markovskie prot︠s︡essy" () by Fizmatgiz () in 1963 and translated to English with the assistance of the author.) * (x+237 pages) (NB. This is a corrected translation of the first Russian edition published as "" by Nauka Press () in 1967 as part of a series on ''Probability Theory and Mathematical Statistics'' () with the assistance of the authors. It is based on lectures held at the
Moscow State University
Moscow State University (MSU), officially M. V. Lomonosov Moscow State University,. is a public university, public research university in Moscow, Russia. The university includes 15 research institutes, 43 faculties, more than 300 departments, a ...
in 1962/1963.)
*
*
* (4 pages)
* (4 pages); (4 of xiv+373+17 pages)
* (xvi+421 pages)
* (4 pages)
* (6 pages)
* (1+10 pages)
*
* (8 pages)
*
*
*(2 pages) * (10 pages) * (18 pages) * (23 pages) *
https://web.archive.org/web/20221130232206/https://www.qualitydigest.com/inside/lean-column/pdca-and-roads-rome-061416.html] * * (1+xvii+1+152 pages) * (13 pages) * (17 pages) (NB. This source does not mention Dynkin or Kruskal specifically.)
External links
* 3:40* * {{cite web , title=Kruskal Principle , editor-first=Denis , editor-last=Behr , date=2023 , work=Conjuring Archive , url=https://www.conjuringarchive.com/list/category/1808 , access-date=2023-09-10 , url-status=live , archive-url=https://web.archive.org/web/20230910083843/https://www.conjuringarchive.com/list/category/1808 , archive-date=2023-09-10 Recreational mathematics Cryptography Number theoretic algorithms Markov models