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

Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

math.dartmouth.edu

Post reply on HN
Print view View original

31–40 of 220 posts

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#31

Post by rntz »

agf wrote: post #28
rntz wrote: post #26

Earlier quoted context omitted.

Couldn't I start in a "tail" leading to a cycle that doesn't include my name? Suppose my name is "A", and I proceed: check box A - read name B; check box B - read name C; check box C - read name B and now I'm in a B-C loop, and will never find my name.

Re-read your scenario -- you have both box A and box C containing name B, but the problem statement says each name appears only once. So you can't get into cycles like this.

Ah, of course! That guarantees there are no "tails"; every name (& box) is part of exactly one cycle. And this is then a property of cycles of permutations generally. Thanks!

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#32

Post by maxerickson »

mkagenius wrote: post #4

Thank god I could solve "Love in Kleptopia". Would have been embarrassing being a founder of a security company.

Interesting to me that there is an analogy with a 1000 year old puzzle.

https://en.wikipedia.org/wiki/Fox,_goose_and_bag_of_beans_pu...

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#34

Post by mcherm »

StavrosK wrote: post #16
craigsmansion wrote: post #15

Earlier quoted context omitted.

> Maria mails Jan one of her padlocks I think the idea is that that padlock would get stolen unless it would be sent in a padlocked box.

I don't know, why would someone steal a padlock unless it was attached to a box? Maybe so, though.

The wording of the problem is "anything sent through the mail will be stolen unless it is enclosed in a padlocked box".

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#35

Post by thomasahle »

hundt wrote: post #23
jfries wrote: post #17

SPOILER 1 Names in boxes I don't understand how this works. The answer says it works to a certain percentage if there are no cycles longer than 50. But even if chance has it that there are two cycles of length 50. Then it seems the chance would be very large that one of the 100 prisoners would en up in the "wrong" loop and thus not find their name?

It's because you start with the box labeled (via the initial random labeling) with your name. If you cycle back to it then it means that you found your name on a piece of paper, since the next box you open is always the one matching the piece of paper in the last box. So it is impossible to start in a cycle that doesn't include your name.

Do you have any intuition to why it helps to build the query sequence on the data? It seems natural that if you have to plan the queries for everybody in advance, you can't do better than 2^(-100) or perhaps (50!)^2/100!. Yet somehow by using the return values to find our next query point we can do much better. Blows my mind.

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#36

Post by lann »

craigsmansion wrote: post #15
StavrosK wrote: post #12

Earlier quoted context omitted.

I knew "the" solution was something DH-like, but my solution was: Maria mails Jan one of her padlocks, and he mails her the ring back in a box that's locked by that padlock. ...I think others are overcomplicating this.

> Maria mails Jan one of her padlocks I think the idea is that that padlock would get stolen unless it would be sent in a padlocked box.

Or even better: a thief replaces the padlock with one of his own, then later steals the ring.

What you really need is a trusted "padlock authority" that can verify the authenticity of your padlocks...

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#38

Post by sskates »

thomasahle wrote: post #35
hundt wrote: post #23

Earlier quoted context omitted.

It's because you start with the box labeled (via the initial random labeling) with your name. If you cycle back to it then it means that you found your name on a piece of paper, since the next box you open is always the one matching the piece of paper in the last box. So it is impossible to start in a cycle that doesn't include your name.

Do you have any intuition to why it helps to build the query sequence on the data? It seems natural that if you have to plan the queries for everybody in advance, you can't do better than 2^(-100) or perhaps (50!)^2/100!. Yet somehow by using the return values to find our next query point we can do much better. Blows my mind.

Each individual still has a ~50% chance of being unable to find their name using the query sequence protocol. By agreeing to the same query sequence their success modes and failure modes are now linked. If there's a cycle of 51 or greater, all of those individuals in that cycle are guaranteed to fail, while if they're in a cycle of 50 or less, all of those individuals are guaranteed to succeed.

What this protocol does is make it so each individual failure mode is much more likely to overlap with each other failure mode. Correlating the performance of individuals when you have a one fail all fail scenario is a common solution to this type of problem.

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#39

Post by phkahler »

jfries wrote: post #17

SPOILER 1 Names in boxes I don't understand how this works. The answer says it works to a certain percentage if there are no cycles longer than 50. But even if chance has it that there are two cycles of length 50. Then it seems the chance would be very large that one of the 100 prisoners would en up in the "wrong" loop and thus not find their name?

I don't understand the answer at all. Are they suggesting that the prisoners have somehow labeled the boxes? Or do they agree to assign names to the boxes via some other way - like make an alphabetic list of prisoners and assume that is the order of the "names on the boxes"? I suppose I just answered my own question, but I'm still not sure ;-)

Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

#40

Post by adium »

JoeAltmaier wrote: post #8

The 'dot-town suicides' is a more general version of a puzzle I know, "The Island with Blue-Eyed People". The solution is an induction, which is unusual in these kinds of problems.

Why can't the visitor say "There are X red, X blue, and 1 yellow?" No one knows about the yellow, thinks it is themself, they all commit suicide on the spot.
Post reply on HN