The Kruskal Count?

Question

In honor of Martin Kruskal (http://www.latimes.com/news/science/la-me-kruskal6jan06,1,3884010.story?track=rss and http://en.wikipedia.org/wiki/Martin_Kruskal ), whose work on solitons helped create the fiber optic cable, I ask the following:

One of Kruskal's most famous contributions to mathematical literature is called the Kruskal Count, which is, of all things, a card trick. It apparently is related to Markov chains, another thing that I don't really understand.

The Kruskal Count is described in detail in the following paper:

http://arxiv.org/PS_cache/math/pdf/0110/0110143.pdf

10 points to the person who can give the best explanation of how the Kruskal Count card trick works.

I was hoping for something a little more formal than that.

Answer 1

I could explain Kruskal count, but since you have the references to the papers, I presume you have understood the principle. I am giving a very simple example of application of the Kruskal count below. Try it :-)


Look at the three lines of Genesis verse below :

1. In the beginning God created the heaven and the Earth
2. And the Earth was without form, and void; and darkness was upon the face of the deep. And the Spirit of God moved upon the face of the waters.
3. And God said, let there be light, and there was light.

Choose any word from the ten words in the first line.
Count the number of letters in the chosen word, and call this n1.
Then skip ahead to the n1 th word.
Say this next word has n2 number of letters.
Skip to the n2 th word ahead.
Keep doing this till you enter the third line.

Any choice you make out of first ten words, will always terminate in the word GOD in the third line :-)

Example - say one chooses the second "the" in the first line. It has three (=n1) letters. So, we go to "created" which is the 3rd word ahead. Now "created" has 7 letters. So, we reach the "the" in the second line. Similarly, next iteration we reach "without", then "upon", then, "the", then again "the", then "God", then another "the", then one more "the" and you finally arrive at "God" in the third line.

Any of the ten words in first line will always terminate into the "God" :-)

A Kruskal chain with no of words in a text with far far larger than the no of letters in the largest word will have any random two chains intersect at some point, after which they merge. The intersection in the example above takes place at "the". So, for a chain comprised of much larger number of words than the number of letters, all options will intersect somewhere, and then follow the same chain, and hence will terminate in same word.

I hope this was simple, because explaining was not really easy :-)

Answer 2

It's pretty straightforward to understand why "locking in step" is more likely than not. You pick your starting card, the magican picks any other starting card, usually the first one. Both of you begin your sequence of cards, which are determined by the deck. Once the magican's own sequence of cards matches yours at any point, both of you will thereby complete the same sequence for the remainder of the deck. The more cards the deck has, the more likely is it that both of you are going to eventually hit the same card at some point.

An analogy can be found in the theory of finite state automata. Any finite state automata will either 1) enter an endless cycle, or 2) get hung up at a single state. This is regardless of any starting state. The reason is because once a state machine reaches a state it has arrived before, it will repeat.

I've often wondered if this is what happens when in traffic, I find myself following a car who seems to be going EXACTLY where I planned on going, and in my way the whole time. But, nah..

Addendum: Gosh, the formal mathematical estimation of the odds of a match is kind of beyond the scope of this Yahoo! Answers space.

Answer 3

I don't think anyone will write your code for 10 points in Yahoo! Answers. However maybe if you remind us what this algorithm does we can help with program set up. Was this a tree-search for optimization, IIRC?

Answer 4

i dont have an answer, i just like the Q, and want it in my list of answers so i can study it
thx!

Answer 5

just wonder how would others do it.