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

61–70 of 220 posts

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

#61

Post by fengwick3 »

phkahler wrote: post #39
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 ;-)

One assumption not explicitly explained is that the prisoners can identify the boxes by their order, since they are arranged in a line. So, the prisoners first agree among themselves that box number x should correspond to which prisoner, and vice versa. So now, each box contains a name, which points to another box at a certain position, which contains another name, ad infinitum, until the prisoner finds his name. It is guaranteed that he will, because of the relationship between permutations and cycles.

It is interesting that this question is regarded as the most math intensive. I myself was spoiled the solution a few years ago, but I have the impression that the challenge is in observing the correct algorithm rather than calculating the probability. Maybe the author felt that one needs mathematical insights in order to see the solution out of the blue.

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

#62

Post by captaincanoe »

gambiting wrote: post #52
phkahler wrote: post #39

Earlier quoted context omitted.

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 ;-)

Every prisoner assigns every box a random name from the list. Boxes cannot be modified in any way, so every prisoner has to do it on their own. The (unexplained) assumption here is that each prisoner can do that somehow, either in their head or on a piece of paper. It doesn't matter that every prisoner has their own unique assignment of names to boxes. The crucial part here is that it's not guaranteed to work - but i…

If each prisoner randomly labels the boxes in their own (presumably independent) manner, then this strategy fails miserably. In fact, it's equivalent to each prisoner choosing 50 random (unique) boxes.

The solution specifies that "the prisoners must first agree on a random labeling of the boxes by their own names." This is necessary.

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

#63

Post by heartbreak »

cyborgx7 wrote: post #5
mkagenius wrote: post #4

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

I'm mad at myself for not managing to figure this out myself. I guess i made more assumptions about the limitations than there were in the description of the problem.

I think you'd enjoy The Code Book by Simon Singh.

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

#64

Post by adium »

_archon_ wrote: post #56
adium wrote: post #40

Earlier quoted context omitted.

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.

There's a discrepancy between the number of visible blues and the number given. Say the person is a blue and doesn't know it. They can count b-1 blues on everyone else. Hearing "r reds, b blues, 1 yellow," he knows he must be either blue or yellow. He doesn't know which. Everyone survives. Edit: had a paren instead of opening quote.

I'm also thinking it would need to be at least a couple hundred people to be classified as a town. Which then the odds of someone subconsciously counting a number that high in their head is unlikely.

In a classroom with 30 people right now and I couldn't tell you how many of each gender there are unless I actively try. If that meant certain death, why would I count?

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

#65

Post by logfromblammo »

mikeash wrote: post #53
logfromblammo wrote: post #42

Earlier quoted context omitted.

Jan constructs an enormous box around the entire country of Kleptopia, and places his own padlock on it from the inside. Then he mails the ring with no additional security measures. The problem is fatally flawed by not explicitly stating that boxes locked with padlocks are also not stolen, despite not being enclosed in a padlocked box.

Jan takes a normal box and locks it. He declares the space enclosed by the box to be the "outside," and the world to be "inside."

Unfortunately, the mail thieves declare "outside" to be the volume in conformal space on the side of the boundary definition that contains the point at infinity, and "inside" to be the volume that does not, and thus steal the ring.

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

#70

Post by adium »

JoeAltmaier wrote: post #41
adium wrote: post #40

Earlier quoted context omitted.

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.

That sounds about right. But the problem statement doesn't permit the information to be a lie? The info could be "somebody has blue eyes!"

The comment elaborated on the explanation of "non-trivial" and didn't explicitly say you can't lie. Right? Or am I not hearing this correctly?

Some of the questions incorporate a "new idea" or allow you to change elements. Triangle boxes, prisoners who can make requests, tired tennis players.... I introduced a yellow dot or am I supposed to change the variables to two?

Post reply on HN