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.
Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
71–80 of 220 posts
Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#72SPOILER 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?
It's because you start with the box labeled (via the initial random labeling) with your name. If you cycle back to it then it means that you found your name on a piece of paper, since the next box you open is always the one matching the piece of paper in the last box. So it is impossible to start in a cycle that doesn't include your name.
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 same door if it's based on the wall, put the table in the middle of the room.
Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#73Thank god I could solve "Love in Kleptopia". Would have been embarrassing being a founder of a security company.
I'm mad at myself for not managing to figure this out myself. I guess i made more assumptions about the limitations than there were in the description of the problem.
[deleted]
Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#74Thank god I could solve "Love in Kleptopia". Would have been embarrassing being a founder of a security company.
I'm mad at myself for not managing to figure this out myself. I guess i made more assumptions about the limitations than there were in the description of the problem.
Same. It was not clear that multiple padlocks can be added to the box.
Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#75Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#76Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#77Earlier 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…
Yes, not everyone knows that permutations decompose uniquely as products of disjoint cycles.
Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#78The '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.
Why can't the visitor say "There are X red, X blue, and 1 yellow?" No one knows about the yellow, thinks it is themself, they all commit suicide on the spot.
There are many things that the visitor can say, and the question is to prove that absolutely anything that the visitor says will result in complete suicide if it provides any information whatsoever about the dots.
Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#79Ah, 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 unchanged.
After visiting the room, each prisoner is asked if every prisoner has visited the room by now. If he answers 'Yes' and indeed everyone has been to the room at least once, then everybody is freed immediately. Otherwise they are all executed ;) He can answer 'I don't know' without any consequences.
Apart from the lamp being on or off the prisoners have no way of communication at all, but of course as is customary in such puzzles they can plot a strategy in advance and everybody is a perfect logician.
So, to clarify: The goal is for one prisoner to be 100% sure that everybody has been to the room at least once. The "easiest" solution would simply be to wait a few billion years (it's an abstract puzzle, they are all immortal anyways ;). But of course there is a more elegant solution that terminates earlier.
Also, as the time for a visit is chosen at random a prisoner has no way of knowing who the previous person in the room was. It might just as well have been himself!
As there is some randomness involved, it is theoretically possible that the goal state never happens. Just assume that in the limit everybody will have visited the room infinitely often ;)
In other words: Implement synchronization between 100 threads with only one bit of shared memory and completely random scheduling.
Re: Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
#80SPOILER 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?
Minute Physics [1] did a video on the puzzle [2] and the solution [3].
[1] https://www.youtube.com/user/minutephysics/videos