Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Kruskal Count Card Trick

faculty.uml.edu

Post reply on HN
Print view View original

31–40 of 43 posts

Re: The Kruskal Count Card Trick

#31

Post by dahart »

I wonder if this is related -- the description immediately made me think of the "avalanche" effect in hash functions. A hash function avalanches if a single bit change in the input produces a wildly different output. So avalanche would be the exact opposite of the funneling effect of this card counting trick. In hash functions, the funneling effect or "trap card" would be a sign that your counting function isn't good enough. (https://en.wikipedia.org/wiki/Avalanche_effect)

Pretty sure I first heard about avalanching from Bob Jenkins' hash functions. (http://burtleburtle.net/bob/hash/doobs.html)

Re: The Kruskal Count Card Trick

#32

Post by [deleted] »

dalore wrote: post #18
rtpg wrote: post #7

Earlier quoted context omitted.

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.

I think the fact the deck doesn't have many repeats of 9s. It has lots of repeats of 5s which causes merges and the other numbers will eventually merge. You have 4 each of 6,7,8,9. If you repeat 9 4 times there will be no more 9's and it will merge.

[deleted]

Re: The Kruskal Count Card Trick

#33

Post by akrasuski1 »

dahart wrote: post #31

I wonder if this is related -- the description immediately made me think of the "avalanche" effect in hash functions. A hash function avalanches if a single bit change in the input produces a wildly different output. So avalanche would be the exact opposite of the funneling effect of this card counting trick. In hash functions, the funneling effect or "trap card" would be a sign that your counting function isn't good…

It's really unrelated - it's more about the hash domain being rather small, i.e. 52. I would think that if you substitute the counting (go to card N+value) to proper hashing (go to card md5(value)%52) you would get the same, if not stronger, result.

Re: The Kruskal Count Card Trick

#34

Post by rxm »

When I was a graduate student, in the late 80s, I was waiting for a flight to Los Alamos in Albuquerque. There was only one other person in the lounge, obviously also going to Los Alamos. I started chatting and he introduced himself as Martin Kruskal. Idiot me had no idea whom I was speaking to. I said “The only Kruskal I know invented this amazing card trick having to do with dynamical systems.” He stared at me, obviously pleased. “Not many people know my brother and I are into magic.” He did not want to take credit for the trick and attributed it to his brother. He would come often to Los Alamos and I miss chatting with him (got lots of advice on bringing up girls).

Re: The Kruskal Count Card Trick

#35

Post by gowld »

seanalltogether wrote: post #10

Since all face cards count as a 5, does the probability increase or decrease if you remove all face cards?

Decrease. Face cards are overrepresented, so the smaller the value of the face cards, the more likely they are to cause a "path" to "merge" with another nearby number's path.

Re: The Kruskal Count Card Trick

#37

Post by sarosh »

rxm wrote: post #34

When I was a graduate student, in the late 80s, I was waiting for a flight to Los Alamos in Albuquerque. There was only one other person in the lounge, obviously also going to Los Alamos. I started chatting and he introduced himself as Martin Kruskal. Idiot me had no idea whom I was speaking to. I said “The only Kruskal I know invented this amazing card trick having to do with dynamical systems.” He stared at me, obv…

What was the advice?

Re: The Kruskal Count Card Trick

#38

Post by regularfry »

IanCal wrote: post #11
seanalltogether wrote: post #10

Since all face cards count as a 5, does the probability increase or decrease if you remove all face cards?

I put together a small simulation and I think you have an 82% chance of winning with the setup described (though I welcome repeats). Replacing the J/Q/K with a score of 10 and the win rate drops to ~68%. Intuitively anything that makes you take shorter steps should increase the chance of merging with another path.

Try running it again with them set to 2. My bet would be that's also less good than 5 (but not as bad as set to 10). I'd be very interested to know if that's right or not.

Re: The Kruskal Count Card Trick

#40

Post by IanCal »

regularfry wrote: post #38
IanCal wrote: post #11

Earlier quoted context omitted.

I put together a small simulation and I think you have an 82% chance of winning with the setup described (though I welcome repeats). Replacing the J/Q/K with a score of 10 and the win rate drops to ~68%. Intuitively anything that makes you take shorter steps should increase the chance of merging with another path.

Try running it again with them set to 2. My bet would be that's also less good than 5 (but not as bad as set to 10). I'd be very interested to know if that's right or not.

I'll try when I get home but I'd be shocked if that's the case. They're more likely to merge at an earlier point as paths now have shorter jumps.
Post reply on HN