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

111–120 of 220 posts

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

#111

Post by hundt »

adium wrote: post #110
bjornedstrom wrote: post #95

Earlier quoted context omitted.

I coded a simulation here if that helps: https://gist.github.com/bjornedstrom/971574557b6f3179db08350...

The first two times I ran it I got 0.298 and 0.286. Out of 20 attempts 5 were below 30%.

1000 is a pretty small number of trials. Also note the docs on random.shuffle:

Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.[1]

I don't know if we have any reason to believe that the small subset of all permutations that this library can generate is unbiased in terms of the size of the cycles.

https://docs.python.org/2/library/random.html#random.shuffle

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

#113

Post by ajnin »

logfromblammo wrote: post #42
mcherm wrote: post #34

Earlier quoted context omitted.

The wording of the problem is "anything sent through the mail will be stolen unless it is enclosed in a padlocked box".

Jan constructs an enormous box around the entire country of Kleptopia, and places his own padlock on it from the inside. Then he mails the ring with no additional security measures. The problem is fatally flawed by not explicitly stating that boxes locked with padlocks are also not stolen, despite not being enclosed in a padlocked box.

> anything sent through the mail will be stolen unless it is enclosed in a padlocked box

If someone stole the padlocked box then they would necessarily also steal whatever's inside. Therefore (non-empty) padlocked boxes are safe to mail.

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

#114

Post by Guillaume86 »

bjornedstrom wrote: post #95
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...

I also coded a simulation, mine is in js: https://jsfiddle.net/a3ch3s5h/

I only run once, you'll have to run it a few times to get a positive result.

The output is displayed in the js console (F12 on most browsers).

Edit: Something interesting I derived from the solution is that by allowing the first prisoner to reset the experiment if he fails or don't like the result, they get a 100% success rate. The first prisoner just need to wait for an arrangement which place him in a 50 length cycle (which means no other cycle can be of length > 50).

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

#115

Post by pfedak »

cousin_it wrote: post #91
bzbarsky wrote: post #87

Earlier quoted context omitted.

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

I'm having trouble with your "therefore" conclusion. The projection of the perimeter of the inner box could easily be shorter than the sum of the lengths of the projections of each edge. It seems like you need a less obvious (to me, anyway) statement about the projection of a collection of lines.

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

#116

Post by Retric »

mwerty wrote: post #106
Retric wrote: post #72

Earlier quoted context omitted.

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 must be missing something. Couldn't one instead assume that they have a private notebook and a pen? And that they can tell left from right? Seems more reasonable.

So you want to add a private notebook that the warden can't read. Further, left vs right does not help if the table is in the middle of a room and people are entering from random doors.

AKA, the solution assumes a lot of information not explicitly part of the original wording.

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

#117

Post by ythl »

mkagenius wrote: post #4

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

That puzzle needed more clarification. The solution talks about having two padlocks affixed to the same box, but I can't imagine any kind of box that can have 2 padlocks affixed to it unless the box is specifically designed to allow 2 locks.

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

#118

Post by jon_richards »

rntz wrote: post #103
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…

This is indeed the standard solution. There is also a more difficult version: Every prisoner is required to have the same strategy (so you cannot pick a unique person F). (Every thread runs the same program, and threads do not have access to a unique thread identifier.)

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 on the light 99 more times than they turn it off (and then they have to see it off, indicating the 99th person has reached c=0, and turn it on for themself to reach c=101).

Edit: Thinking back through, I think just starting at c=2 and waiting for c=200 works for an uncertain initial state of the light.

Edit 2: One of the problems with this method is that you are essentially waiting for the nature of random distributions to select people unevenly to get people to hit c=0 and be "removed". At higher average c (excluding 0s), this may take a while. It can probably be made faster by having a chance to not turn on the light at low c and not turn off the light at high c, but I wouldn't be surprised if that doesn't actually end up being faster. At the very minimum a prisoner could stop lowering c once it got above the 50% mark.

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

#119

Post by soVeryTired »

fengwick3 wrote: post #61
phkahler wrote: post #39

Earlier quoted context omitted.

I don't understand the answer at all. Are they suggesting that the prisoners have somehow labeled the boxes? Or do they agree to assign names to the boxes via some other way - like make an alphabetic list of prisoners and assume that is the order of the "names on the boxes"? I suppose I just answered my own question, but I'm still not sure ;-)

One assumption not explicitly explained is that the prisoners can identify the boxes by their order, since they are arranged in a line. So, the prisoners first agree among themselves that box number x should correspond to which prisoner, and vice versa. So now, each box contains a name, which points to another box at a certain position, which contains another name, ad infinitum, until the prisoner finds his name. It…

>I have the impression that the challenge is in observing the correct algorithm rather than calculating the probability

I've got a stats PhD and I guessed the solution but couldn't calculate the probability of having a max cycle length of 50 or less. To be fair, the calculation isn't hard once you see it, but it's not trivial either.

The 30% figure threw me since I know the probability of a random permutation having a fixed point is 1/e (just over 30%), so I went looking for ways to link the cycle length to the Poisson distribution.

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

#120

Post by logfromblammo »

ajnin wrote: post #113
logfromblammo wrote: post #42

Earlier quoted context omitted.

Jan constructs an enormous box around the entire country of Kleptopia, and places his own padlock on it from the inside. Then he mails the ring with no additional security measures. The problem is fatally flawed by not explicitly stating that boxes locked with padlocks are also not stolen, despite not being enclosed in a padlocked box.

> anything sent through the mail will be stolen unless it is enclosed in a padlocked box If someone stole the padlocked box then they would necessarily also steal whatever's inside. Therefore (non-empty) padlocked boxes are safe to mail.

Aha!

Then you put a tiny corundum crystal inside a tiny padlocked box, and permanently affix it to the ring. (Or perhaps the ring has a lockable box portion.) Now the ring cannot be stolen without also stealing an object that is inside a padlocked box. Safe to mail.

Post reply on HN