Live data from Hacker News

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

math.dartmouth.edu

201–210 of 220 posts

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

#201
post #150

Earlier quoted context omitted.

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

Or send a bunch of hobbits with the key.

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

#202
post #154

Earlier quoted context omitted.

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.

Yes, you can: the designated prisoner waits until the signal has been fipped n+k times where n is the number of prisoners and k is the number of times the guard can intervene. All other prisoners flip it to that state if it isn't already. See the other replies.

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

#203
post #202

Earlier quoted context omitted.

> 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.

Yes, you can: the designated prisoner waits until the signal has been fipped n+k times where n is the number of prisoners and k is the number of times the guard can intervene. All other prisoners flip it to that state if it isn't already. See the other replies.

That is a completely different strategy than "if we wait long enough, it's bound to work". Waiting is worthless, no matter how long you wait.

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

#204

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…

I agree. If the stranger says something along the lines of, "The number of blue dots is greater than 50." on one day, and on some subsequent day says, "The number of blue dots is not an odd number less than 45." or "The number if blue dots is not a number less than 40 which is divisible by 3.", then no new information will have been conveyed by these latter example statements. I imagine that the stranger could keep stringing them along like this for quite some time, and if multiple statements referring to the same subset were allowed (ex: "The number of blues is not a number which is divisible by 37 which is less than 45." and "The number of blues is not 37.") then the stranger could continue this indefinitely.

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

#205

Earlier quoted context omitted.

>What does it matter? Are you saying there is no other way? Why don't you give it a try yourself, it's not hard. For starters, just try replacing "they" with "F". Lol. It does matter because you are bitching about using they when you don't even say what on earth are we supposed to say instead. Replace they with the name? "If the light is on when Franklin gets to the room, Franklin turns the light off, and Franklin in…

So, my personal ability to rephrase the sentence is attacked, the pretense that there would be no alternatives is kept and my idea is dismissed as petty. That's just as expected. Note that the above sentence is written in the objective way that I mentioned before. There is no way a third person singular gendered pronoun could creep in there, even if I was talking about you in the third person. Unless Franklin was a t…

Yes, your alternative of simply repeating the noun several times instead of using a pronoun, which you avoid using because you feel its gender neutrality is a tool of the "transfinite gender fluid sjw brigade", despite being in use for 600 years now, is a petty solution indeed.

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

#206

Earlier quoted context omitted.

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.

Ah, I see. Yes, I agree that given that fact you get the desired inequality. But this fact is, as you say, nontrivial. It's certainly false for various non-box-like shapes afaict, so there's something special to boxes that needs proving here.

Just note that all combinations ±a±b±c can be realized by paths on the box.

I'm sorry, I see now that my original comment glossed over tons of stuff that was clear only to me. Instead of saying "easy to check" I should've posted my napkin sketch with the easy check.

Anyway, my solution is still simpler and more natural than the one in that pdf :-)

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

#207
post #202

Earlier quoted context omitted.

Yes, you can: the designated prisoner waits until the signal has been fipped n+k times where n is the number of prisoners and k is the number of times the guard can intervene. All other prisoners flip it to that state if it isn't already. See the other replies.

That is a completely different strategy than "if we wait long enough, it's bound to work". Waiting is worthless, no matter how long you wait.

But under the corrected assumption about the problem, you can reliably know when it is safe to say that all prisoners have been in the room and when you should keep deferring. In the other version of the problem, I agree there's no such guarantee; hence why I bought up the difference.

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

#208

Earlier quoted context omitted.

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.

The chain would start:

    Box - J - Lid
Maria adds hers:

    Box - J - Lid
          |   
          M
Jan can open his padlock, releasing hers, and transform this to:

   Box - J - M - J - Lid
Which Maria can open. An optimization could be:

    Box - M - J - Lid
This is available if Maria could fit her padlock through the port in the box simultaneously with Jan's there, and send that back so Jan could remove his initial box padlock.

And the arrangement

    Box - M - J - Lid
          |   |
          J   M 
Would let either start a new box, using the J - M - J or M - J - M chaining as needed.

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

#209
post #194

Earlier quoted context omitted.

Can you post the solution to the numbered hats one?

Sure. Call the sum of all assigned numbers N. No prisoner knows N, but they do know that there are exactly 100 possible last two digits of N, from "00" up to "99". Beforehand, assign a different last digit pair to each prisoner. When the prisoner guesses, he sums everybody else's number, then guesses the number between 1 and 100 that, when added to his partial sum, results in his assigned last two digits.

That's much cleaner than I thought it would be. I was convinced that there was a solution that guaranteed success, since each arrangement of numbers could get mapped to a unique guessing strategy, so if you could make it so that exactly one correct guess per arrangement you're golden. I tried working with a N-wide N-dimensional cube, got it working for N=2, and failed at N=3.

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

#210
post #170

Earlier quoted context omitted.

Why does each person need to enter the room twice? F is allowed to turn the light off, each other person can only turn the light on ONCE. Every time F enters and the light is ON he turns it off and increments his counter. When F's count gets to 100 they go free (99 turned it on ONCE and there was at most one false positive) and, obviously, F has entered at least 100 times.

If the initial state of the light is known to F then you only need once per person. However if the initial state of the light is unknown to F then your proposal would deadlock at 99 wherever the light starts off, because it will only ever be turned on 99 times, so 100 will never be reached. The twice entry solution avoids this issue because if the light starts on then the most that 98 people will turn it on is 196 ti…

[deleted]
Post reply on HN