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

181–190 of 220 posts

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

#181

Post by twhb »

evanb wrote: post #175
twhb wrote: post #148

I collect riddles like these! Here are a few of them. Numbered Hats A warden places a hat on the head of each of 100 prisoners, each with a random number from 1 to 100. There may be duplicates. Each prisoner can see everybody's hat but their own. Each prisoner then guesses their own number; if any guess correctly, they all go free. The group may not communicate in any way during the trial, but may strategize beforeha…

Numbered hats: I'm not sure this is optimal. When the prisoners are together, they assign each person a unique ID from 1 to 100. Once the round starts, each looks around and adds up the total on everybody else's hat, mod 100. Suppose you see a total of h (mod 100). Then you should make a guess g = h - your ID (mod 100). With 1000 repeated experiments of 1000 trials each, this saved the prisoners ~ 630±17 ~= 63±2 perc…

There's a strategy that guarantees success. And you're so very close to it. So close, in fact, that I'm going to guess you've heard this before and just don't fully remember the solution.

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

#182

Post by alanbernstein »

yorwba wrote: post #81
alanbernstein wrote: post #54

Earlier quoted context omitted.

I don't quite follow the solution, can anyone explain a bit more? What's the motivation for considering large epsilon?

The rigorous version would be: 0 The limit for ε to infinity must be >= 0 and is ((a+b+c) - (a'+b'+c'))π, therefore a+b+c >= a'+b'+c'. "large epsilon" is a standard way to express "consider the asymptotic behavior for epsilon to infinity and you will see what I mean".

Thanks, I get that it means asymptotic behavior - that's the thing I don't get the motivation for.

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

#183

Post by raziel414 »

twhb wrote: post #148

I collect riddles like these! Here are a few of them. Numbered Hats A warden places a hat on the head of each of 100 prisoners, each with a random number from 1 to 100. There may be duplicates. Each prisoner can see everybody's hat but their own. Each prisoner then guesses their own number; if any guess correctly, they all go free. The group may not communicate in any way during the trial, but may strategize beforeha…

Can you post the solution to the numbered hats one?

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

#184

Post by panic »

alanbernstein wrote: post #182
yorwba wrote: post #81

Earlier quoted context omitted.

The rigorous version would be: 0 The limit for ε to infinity must be >= 0 and is ((a+b+c) - (a'+b'+c'))π, therefore a+b+c >= a'+b'+c'. "large epsilon" is a standard way to express "consider the asymptotic behavior for epsilon to infinity and you will see what I mean".

Thanks, I get that it means asymptotic behavior - that's the thing I don't get the motivation for.

I think the intuition is that we want to focus on the edges of the box (where the lengths sum together like the answer we're looking for), not the volume (where the lengths multiply together and cause problems). So we expand the edges until they completely dominate the equation.

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

#185

Post by fenomas »

albinofrenchy wrote: post #128
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.

I think the puzzle as phrased is slightly incomplete. The stranger must communicate something _new_ each day to make the induction work. For instance, if the number of blues is 25, and the (merciful) stranger says that the number of blues is not prime every day, no one ever has enough information. And in fact, even that doesn't seem to be enough. The non-trivial part must be that at least one person knows more than t…

You are overlooking that all the residents gather together each day. Once a visitor has said something nontrivial, after that the new information each day comes when the residents gather, and discover who did or didn't commit suicide the night before.

Also:

> For instance, if the number of blues is 25, and the (merciful) stranger says that the number of blues is not prime every day, no one ever has enough information.

This is not correct. Saying "the number of blues isn't prime" just once would be sufficient to start the process, as would "there is at least one blue", etc. It doesn't matter that it's not new information to any one villager.

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

#186

Post by fenomas »

Retric wrote: post #72
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.

It assumes, they can secretly assign and remember a 100 items random ordering and then execute it perfectly. Further, it assumes they can decide which orientation is the start vs end of the line. Thus, it's not actually possible, but 'in theory' it seems to work. EX: If I know your going to order based on which side is closet to the entry door nob when the door is closed. Well nothing says they all enter from the sam…

I agree that the puzzle sort of plays dirty pool here.

The strict requirement is that the boxes are distinguishable. The puzzle implies this by saying they're lined up on a table, but it would be more honest to the reader to say they're numbered 1-100, or somesuch.

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

#187

Post by mkagenius »

LeifCarrotson wrote: post #131
mkagenius wrote: post #4

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

I solved it a little differently than the suggested method. The suggested solution requires a box that is capable of being locked in both the lid and box by two padlocks. It also requires (Spoiler!) the ring to make two pointless transits, which could be expensive if it was large. What if, instead, the box was capable of admitting only one padlock? Then Jan would padlock it closed. On receiving the locked box, Maria…

> Jan can form a chain that can be broken by either his padlocks or by Maria's padlock

The box cannot be opened by Maria, breaking the rear end of chain wouldn't help at all.

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

#188

Post by cousin_it »

bzbarsky wrote: post #164
cousin_it wrote: post #160

Earlier quoted context omitted.

See response to pfedak.

I'm still not quite following. Is the "perimeter" here the sum of the lengths of projections of the edges, then how is that different from "the sum of its projections"? Anyway if you define "perimeter" that way then for the outer box the "perimeter" is in fact 4 * (a+b+c), where a, b, c are the dimensions of the box. I also agree that for the inner box the "perimeter" is at least 4 * (a'+b'+c'), by the triangle inequ…

Let's say the projections of the inner box's edges onto the X axis have three distinct lengths a,b,c (all positive). Also let's say the distance between the leftmost and rightmost projected vertices is d. The nontrivial fact is that d=a+b+c, and not say a-b+c. That leads to the desired inequality, I think.

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

#189

Post by OscarCunningham »

logfromblammo wrote: post #65
mikeash wrote: post #53

Earlier quoted context omitted.

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.

Of course the point at infinity had been stolen some time ago, and its whereabouts are currently unknown.

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

#190

Post by thaumasiotes »

SilasX wrote: post #154
thaumasiotes wrote: post #146

Earlier quoted context omitted.

So? It doesn't have to be true that each prisoner will be visited within any particular time frame.

The solution only requires that they will eventually be visited; you can keep deferring until they are. There's no specific time frame in which you have to make a guess.

> There's no specific time frame in which you have to make a guess

This is correct.

> The solution only requires that they will eventually be visited; you can keep deferring until they are.

This is false; you can't "keep deferring until everyone is visited" because you have no way of assessing whether that's happened. As a strategy, it is impossible to implement.

Post reply on HN