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

211–220 of 220 posts

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

#211

Post by Tloewald »

aiiane wrote: post #170
Tloewald wrote: post #168

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…

The 198 solution has the same problem. F cannot tell if the light is on because it was originally on, or G preceded F and the light started off. You're always going to be susceptible to off-by-one errors.

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

#212

Post by mkagenius »

LeifCarrotson wrote: post #208
mkagenius wrote: post #187

Earlier quoted context omitted.

> 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 B…

Nicely done. Understood the chaining solution now. One small assumption in that would be that the chain remains taut enough to not leave any gaps to slide the hands into the box (since the lid's hook is no longer in touch with the box).

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

#213

Post by [deleted] »

twhb wrote: post #181
evanb wrote: post #175

Earlier quoted context omitted.

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.

[deleted]

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

#214

Post by posterboy »

andrepd wrote: post #205
posterboy wrote: post #192

Earlier quoted context omitted.

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.

The first sentence of my last comment was what I had called objective. All the while, going by the repeated mentioning of me, ie. "you", the answer I got seemed much more focused on me. Well, I'm very egoistic, going by my mentioning myself so often here, so I'm flattered by your attention, but I suppose you are missing the point.

Nice talking to you, thanks for the link.

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

#215

Post by fenomas »

thebrainkid wrote: post #204
albinofrenchy wrote: post #128

Earlier quoted context omitted.

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 s…

The puzzle doesn't involve the stranger saying multiple things. He just shows up, says one thing that everyone already knows to be true (e.g. "At least one of you has blue eyes"), and then leaves forever. And that's enough to cause everyone to (eventually) commit suicide.

The fact that this happens even though it doesn't sound like new information is what makes it an interesting puzzle!

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

#216

Post by JoeAltmaier »

tiglionabbit wrote: post #179
x1798DE wrote: post #162

Earlier quoted context omitted.

> If two people have blue eyes, "Somebody has blue eyes" is not new information, because everyone has already seen that someone has blue eyes. The new information in that scenario is that the other guy with blue eyes knows that someone has blue eyes.

If they have seen someone with blue eyes they would already know that.

They know that you know that. That's the new info.

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

#217

Post by foxfaction »

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?

But why would that matter? You don't know 89 has your name in it, because the numbers were randomly assigned to random people in the first place. You would just draw the name associated with box 89, which is not necessarily your name.

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

#218

Post by jon_richards »

thomasahle wrote: post #198
jon_richards wrote: post #118

Earlier quoted context omitted.

I'll just solve this assuming the light starts off, because otherwise I have a feeling it will get miserable to think through. Every prisoner starts at c=1. If light is on, turn it off and decrement c. If the light is off, turn it on and increment c. It c hits 0, always do nothing. If c=101, everyone has been to the room. Everyone wants to turn off 1 more light than they turn on, but that means one person has to turn…

Very nice solution. I wonder if it can be made not rely on randomness at all. The 'standard' solution just required that every prisoner would be taken to the room infinitely many times. As long as this was the case, the warden could try any devious sequence they liked.

Interesting question. Haven't solved it yet, but it did give me an idea for an optimization.

If the prisoner stores c_max, they can decide to only ever turn off the light (until c=0) if c This is because there is at least 1 other prisoner still turning on the light (they could turn off the light they turned on to reach c = c_max - 1, but only get lower if someone else turns on the light for them).

Unfortunately an adversarial sequence still hangs progress, as prisoners can be juggled between c_max and c_max-1.

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

#219

Post by pkroll »

jonahx wrote: post #139
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.

This just isn't true. I mean, yes they exist, but the norm is overwhelmingly a single latch with room for a single lock.

Without a third party showing sales of padlock boxes with and without space for two or more locks, there's no actual way of being SURE which is more common.

Even if there are ten times as many boxes available that only have space for a single lock, what matters in the case of the puzzle is, a box with space for two or more locks is readily available. Suggesting in the puzzle "by the way the box has space for two locks" really kind of destroys the "puzzle" aspect.

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

#220

Post by Tycho »

foxfaction wrote: post #217
hundt wrote: post #138

Earlier quoted context omitted.

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?

But why would that matter? You don't know 89 has your name in it, because the numbers were randomly assigned to random people in the first place. You would just draw the name associated with box 89, which is not necessarily your name.

Whatever box you open, you take the name inside and go to the number you associated with that name. So when you end up at box 89, the last box you opened must have had your name inside. So you will have found your name, provided you got there in under 50 steps.
Post reply on HN