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

141–150 of 220 posts

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

#141

Post by mikeash »

ythl wrote: post #133
pkroll wrote: post #126

Earlier quoted context omitted.

A quick search for padlocked box will show many, many such boxes. It seems more common for there to be space for two or more locks, than for just one.

My point is that the puzzle should be updated to inform the reader that designing the right kind of box is a part of the puzzle: "Jan and Maria each have plenty of padlocks, but none to which the other has a key. Using only the padlocks, keys, and a custom-designed box, how can Jan get the ring safely into Maria’s hands?"

You could always take a one-lock box and build an adapter that accepts two locks, and keeps the box locked if either lock is present.

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

#142

Post by mikeash »

joveian wrote: post #99
mkagenius wrote: post #4

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

:). OTOH, as someone interested in high latency communication protocols I wish cryptographers would hesitate to suggest a three round trip protocol at postal latency. My solution is that Jan should send the ring in a padlocked wooden box with an inner protective but unlocked box and Maria should apply a saw to the outer box. (To be fair, I can certainly imagine that in Kleptopia they know how to make excellent boxes)…

Even simpler: send it in a padlocked cardboard box which Maria can rip open with her hands. Nothing in the problem statement says that the box itself has to be resistant to attack.

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

#143

Post by justinpombrio »

iliis wrote: post #79

Ah, I love these kind of puzzles! Here's another one, similiar to the first one (Names in Boxes). Apologies for any incorrections in advance. There are 100 prisoners. At random times one prisoner is chosen uniformly at random and led into a room with a single lamp. The prisoner can choose to switch it on or off or leave it as the last visiting prisoner left it. Apart from the state of the lamp he must leave the room…

Here's a much harder variation. There are three changes:

(1) No prisoner is distinguishable from any other. In other words, they must all have the same strategy.

(2) The prisoners are all given coins, so that they can make random decisions.

(3) The goal is now to find a strategy that will eventually halt with probability 1 (in other words, how long it takes can depend on the coin flips, but any run that takes infinite time must happen only with probability 0). However, the prisoners are not allowed to take chances when answering "yes"; they can only say "yes" if they are certain that every prisoner has visited the room.

It has a very elegant solution.

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

#145

Post by SilasX »

hundt wrote: post #138
SilasX wrote: post #132

Earlier quoted context omitted.

I guess that's what I'm confused about: when we start, the boxes we map our names to have nothing to do with the name in the box. Just because my cycle includes the box I got assigned to, doesn't mean that cycle includes the box with my name inside it. If my name maps to 89, then sure, I accept 89 is a LT-50 cycle, but why does it mean that that cycle actually contains my name (as opposed to the box we assigned me to…

Think about how you will get back to the box you got assigned to. Like what do you have to see in order to return to box 89, where you started?

Ah, okay, that makes more sense. So the solution is to impose a random ordering on the (1-100 random numbers assigned to the) boxes that ensures you will return to the first one you picked, and that the one that points to your initial pick (or your initial pick itself) has your name in it.

This ordering then partitions the boxes into cycles where each prisoner is in their cycle, and has a low chance of having 50-sized cycles.

Still mesmerized at how the choice of query can improve your chances like that without accumulating information.

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

#146

Post by thaumasiotes »

SilasX wrote: post #90
dsugarman wrote: post #83

Earlier quoted context omitted.

>The "easiest" solution would simply be to wait a few billion years Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time. Of course the probability will get higher and higher that everyone was in the room once if it was completely random but that probability will never be 100%. I know of two legitimate answers to this problem, it took me aw…

>Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time. IIRC, in the original statement of the problem, there's also a stipulation that, for all prisoners, the king/chooser/whatever will visit them an infinite number of times (so at any time it must be true that each prisoner will be visited [again or for the first time] if the game doesn't…

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

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

#147

Post by posterboy »

andrepd wrote: post #137
posterboy wrote: post #130

Earlier quoted context omitted.

> If the light is on when F gets to the room, they turn the light off, and they increment their counter. Who is they???

https://en.wikipedia.org/wiki/Singular_they

Good grief. If you want to write objective, do so, and ommit personal pronouns all together, but don't employ this archaic, confusing grammatical quirk. I'd like to point out to you, ekke's comment was much better understandable and shorter.

Edit: Did you even read what you linked?

> One explanation given for some uses of they referring to a singular antecedent is notional agreement, when the antecedent is seen as semantically plural

F was definitely singular.

> Distributive constructions apply a single idea to multiple members of a group. They are typically marked in English by words like each, every and any.

That is indeed something I often wondered about, sadly that part is inconclusive.

> Referential and non-referential anaphors

I didn't even try to read. That looks like it should be it's own article.

> On the other hand, when the pronoun they was used to refer to known individuals ("referential antecedents, for which the gender was presumably known", e.g my nurse, that truck driver, a runner I knew), reading was slowed when compared with use of a gendered pronoun consistent with the "stereotypic gender" (e.g. he for a specific truck driver).

You might ommit personal pronouns, as I said, or use 'it' on the object of the sentence using passive verbs.

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

#148

Post by twhb »

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 beforehand. What strategy has the best chance of success?

Colored Hats

A warden lines up a group of 30 prisoners so they can see everybody in front of them and nobody behind them, then places either a red or a blue hat on each of their heads, randomly. He then goes from the back of the line to the front, telling each prisoner to guess the color of their own hat. Each who guesses correctly is freed. The prisoners cannot see the color of their own hat, and cannot communicate with each other, but can hear each others' guesses and can strategize beforehand. What strategy saves the greatest number of prisoners?

Coins on a Chessboard

A warden takes prisoner A into a room containing a chessboard, on each square of which is a coin randomly showing heads or tails. He then indicates a random square on that board. Prisoner A is given the chance to flip one coin (or none), then taken from the room, after which prisoner B is taken into the room and must say which square the warden indicated. The two prisoners may strategize beforehand, but may not communicate during the trial (except with the single coin flip). What should be their strategy?

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

#149

Post by JoeAltmaier »

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…

The clock is certainly necessary. But for information, I think its as easy as "somebody has blue eyes!" said once. If only one person has blue eyes, they see no one else with blue eyes so kill themselves. If two people have blue eyes, they see the other guy and think "maybe its only him". Next day, that guy is still alive; they now know the only remaining blue-eye is themselves; midnight comes and they both suicide. Then nobody else has to - the two guys died on day 2 so only 2 blue-eyes can exist. And so on.

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

#150

Post by cobalt »

mikeash wrote: post #142
joveian wrote: post #99

Earlier quoted context omitted.

:). OTOH, as someone interested in high latency communication protocols I wish cryptographers would hesitate to suggest a three round trip protocol at postal latency. My solution is that Jan should send the ring in a padlocked wooden box with an inner protective but unlocked box and Maria should apply a saw to the outer box. (To be fair, I can certainly imagine that in Kleptopia they know how to make excellent boxes)…

Even simpler: send it in a padlocked cardboard box which Maria can rip open with her hands. Nothing in the problem statement says that the box itself has to be resistant to attack.

Simplest, drive her the key
Post reply on HN