Kruskal count
From Wikipedia, the free encyclopedia
The Kruskal count[1][2] (also known as Kruskal's principle,[3][4][5][6][7] Dynkin–Kruskal count,[8] Dynkin's counting trick,[9] Dynkin's card trick,[10][11][12][13] coupling card trick[14][15][16] or shift coupling[10][11][12][13]) is a probabilistic concept originally demonstrated by the Russian mathematician Evgenii Borisovich Dynkin in the 1950s or 1960s[when?] discussing coupling effects[14][15][9][16] and rediscovered as a card trick by the American mathematician Martin David Kruskal in the early 1970s[17][nb 1] as a side-product while working on another problem.[18] It was published by Kruskal's friend[19] Martin Gardner[20][1] and magician Karl Fulves in 1975.[21] This is related to a similar trick published by magician Alexander F. Kraus in 1957 as Sum total[22][23][24][25] and later called Kraus principle.[2][7][25][18]
Besides uses as a card trick, the underlying phenomenon has applications in cryptography, code breaking, software tamper protection, code self-synchronization, control-flow resynchronization, design of variable-length codes and variable-length instruction sets, web navigation, object alignment, and others.