The Kruskal Count Card Trick
faculty.uml.edu
The Kruskal Count Card Trick
1–10 of 43 posts
Re: The Kruskal Count Card Trick
#2this is super interesting! The deeper explanation[0] really gets to the essence of what's happening here.
An interesting corrolary: the deeper down the deck you go, the less number of paths are actually available. For example, if you have 10 cards on the first row, then there are at most 10 paths to the end, but those can merge. So if you have many cards, paths will merge and you might just end up with one path.
So most cards towards the end of the deck are totally unreachable! For example the next to last card is most likely not reachable through this walking algorithm in most distributions.
I'm not sure of the implications but it sure feels important for things like randomly generated worlds or whatnot.
[0]: http://faculty.uml.edu/rmontenegro/research/kruskal_count/in...
Re: The Kruskal Count Card Trick
#3this is super interesting! The deeper explanation[0] really gets to the essence of what's happening here. An interesting corrolary: the deeper down the deck you go, the less number of paths are actually available. For example, if you have 10 cards on the first row, then there are at most 10 paths to the end, but those can merge. So if you have many cards, paths will merge and you might just end up with one path. So m…
I don't really see an explanation for the crucial fact that walks merge, which together with the fact that walks can't diverge means that the 1/10 chance of picking the same card at the start invariably increases towards the end.
Re: The Kruskal Count Card Trick
#4this is super interesting! The deeper explanation[0] really gets to the essence of what's happening here. An interesting corrolary: the deeper down the deck you go, the less number of paths are actually available. For example, if you have 10 cards on the first row, then there are at most 10 paths to the end, but those can merge. So if you have many cards, paths will merge and you might just end up with one path. So m…
> For example, if you have 10 cards on the first row, then there are at most 10 paths to the end, but those can merge
In fact they must converge, suppose that the first card on the first row is less than 10, then it will merge with another path on the first move (because it will land on the first row), so it must be 10 to have no merging paths. The next card will merge with another path on the first row if it's less than 9, but if it's 9 it will merge with the first path, so it too must be 10. Same reasoning goes for the third, fourth and fifth card, however there are only 4 cards with value 10, so at least two of the paths on the first row merge within one move.
Re: The Kruskal Count Card Trick
#5The page says that a two deck version of this has a 95% chance of working - does anyone know what % chance the single deck version has?
Re: The Kruskal Count Card Trick
#6The page says that a two deck version of this has a 95% chance of working - does anyone know what % chance the single deck version has?
It says 80% in the text
Re: The Kruskal Count Card Trick
#7this is super interesting! The deeper explanation[0] really gets to the essence of what's happening here. An interesting corrolary: the deeper down the deck you go, the less number of paths are actually available. For example, if you have 10 cards on the first row, then there are at most 10 paths to the end, but those can merge. So if you have many cards, paths will merge and you might just end up with one path. So m…
> For example, if you have 10 cards on the first row, then there are at most 10 paths to the end, but those can merge In fact they must converge, suppose that the first card on the first row is less than 10, then it will merge with another path on the first move (because it will land on the first row), so it must be 10 to have no merging paths. The next card will merge with another path on the first row if it's less…
the fact that they must merge is really dependent on the distribution of cards within the deck, though. For example, imagine if your deck was filled with 9s. You would get 2 paths merging but not much else.
Of course with the standard 52-pack you'll end up with a high degree of merging. I just think it's important to say that the necessity of merging is really dependent on the instruction set, so to speak.
Re: The Kruskal Count Card Trick
#8Re: The Kruskal Count Card Trick
#9this is super interesting! The deeper explanation[0] really gets to the essence of what's happening here. An interesting corrolary: the deeper down the deck you go, the less number of paths are actually available. For example, if you have 10 cards on the first row, then there are at most 10 paths to the end, but those can merge. So if you have many cards, paths will merge and you might just end up with one path. So m…
I don't really see an explanation for the crucial fact that walks merge, which together with the fact that walks can't diverge means that the 1/10 chance of picking the same card at the start invariably increases towards the end.
>. Their walker is equally likely to be on any type of card from the deck (it was shuffled), so there is at least a 1/13 chance of stepping to the spot your walk visited. Since you both use the same rule for taking steps then they will subsequently continue along the same route as your walker and so end at the same card
Re: The Kruskal Count Card Trick
#10Since all face cards count as a 5, does the probability increase or decrease if you remove all face cards?