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

91–100 of 220 posts

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

#91

Post by cousin_it »

bzbarsky wrote: post #87
cousin_it wrote: post #71

I think there's a simpler solution to boxes in boxes. Assume that the outer box is axis-aligned. Project both boxes onto the X axis, so they become one-dimensional. It's easy to check that the "projected perimeter" of the inner box is smaller. Repeat for axes Y and Z. From that and the triangle inequality, the result follows.

Can you expand on this last step? it's not obvious to me what you're applying the triangle inequality to and why it gives the desired result.

The length of a line segment can't be greater than the sum of its projections onto all three axes. Therefore the "perimeter" of the inner box can't be greater than the sum of its projections. But that sum is bounded from above by the "perimeter" of the outer box (which is equal to the sum of its own projections, because the outer box is axis-aligned).

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

#92

Post by ekke »

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…

Good one!

A naive strategy where they never die, and hopefully stay in prison for slightly less than a few billion years:

One prisoner is the light-counter (Mr C). Others follow a simple pattern - if the light is off, and they have never turned it on yet, turn it on. If it is already on, or they have already ever turned it on, do nothing.

Mr C enters the room, if the light is on, remembers it, and turns it off.

When Mr C has entered the room 99 times with light on, he can say 'Yes' and they are safe.

This can be optimized. How?

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

#93

Post by evanb »

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…

Let F be the only person who is permitted to turn the light oFF. The N be every body else---they will be turning the lights oN.

F starts with a counter at 0. If the light is on when F gets to the room, they turn the light off, and they increment their counter. If the light is off when F gets to the room, do nothing.

Each N starts with a counter at 2. When any N enters the room, if the light is on, do nothing, but if their counter is more than 0 and the light is off, turn it on and decrement their counter.

If the light starts on, F will turn it off once, putting their counter at 1. Then, if their counter gets to 198 = 1 + 197, they will know all 99 N people has been in the room once, (and will be certain all but one have been twice).

If the light starts off, some N will turn it on. F's counter gets to 198 when everybody else has been in the room at least twice.

If any prisoner is queried, they should answer "I don't know" unless they are F and their counter is at 198.

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

#95

Post by bjornedstrom »

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 coded a simulation here if that helps: https://gist.github.com/bjornedstrom/971574557b6f3179db08350...

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

#96

Post by TylerE »

evanb wrote: post #93
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…

Let F be the only person who is permitted to turn the light oFF. The N be every body else---they will be turning the lights oN. F starts with a counter at 0. If the light is on when F gets to the room, they turn the light off, and they increment their counter. If the light is off when F gets to the room, do nothing. Each N starts with a counter at 2. When any N enters the room, if the light is on, do nothing, but if…

That's way more than one bit of state!

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

#97

Post by Ensorceled »

Avshalom wrote: post #3
Ensorceled wrote: post #2

For #1, I didn't hear correctly because I didn't understand that the clearly insane and cruel warden would let the prisoners label the boxes before hand :-/

You don't actually need to label them you just need all the prisoners to be able to memorize which name is associated with which box, Alice's box is the first on the left, Bob's the second etc... Then when Zach. Z. Z. Vanderwall opens "his box" and finds the name Bob he follows procedure. You need a minimal perfect hash function but it's a thing that can be done, especially because prisoners in these sort of conundru…

Doh! Of course. But now the recommended solution is really overkill ...

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

#98

Post by mkagenius »

delinka wrote: post #84
mkagenius wrote: post #4

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

I noticed that one proposed solution is pretty pointless: attach a key to the hasp of the first locked box. The key can then be copied ("stolen" in today's copyrights-holder's parlance) by anyone along the mailing route, and the first person to use the key gets the ring. This, aside from the fact that the key on the hasp is not "inside a padlocked box" ...

You are right. Sending key is bad idea.

Another alternate solution was a bummer..

> Win at Wimbleton > 9999-9997 : Roger was wearing himself out

I mean, seriously?

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

#99

Post by joveian »

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

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

#100

Post by kd0amg »

TylerE wrote: post #96
evanb wrote: post #93

Earlier quoted context omitted.

Let F be the only person who is permitted to turn the light oFF. The N be every body else---they will be turning the lights oN. F starts with a counter at 0. If the light is on when F gets to the room, they turn the light off, and they increment their counter. If the light is off when F gets to the room, do nothing. Each N starts with a counter at 2. When any N enters the room, if the light is on, do nothing, but if…

That's way more than one bit of state!

Sure, but the extra is all local state. It still only uses one bit of shared state.
Post reply on HN