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

121–130 of 220 posts

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

#121

Post by greendude29 »

ekke wrote: post #92
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…

This is essentially the same solution I came up with. I'm not sure it needs to be optimized assuming we can set the starting state and the strategy for every prisoner.

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

#122

Post by alphaBetaGamma »

A different solution to the Box in box problem, with less math:

Consider the square of (length + with + height). The sum of the diagonal terms is the square of the distance between opposite corners, the sum of the off diagonal terms equals half the area of the boxes. We can show that both these terms are smaller for the innermost box.

It’s obvious for the diagonal terms, as the opposite corners of a box are the two points of the box that are furthest apart. So the opposite corners of the inner box must be separated by less than the opposite corners of the outer one.

For the cross diagonal terms: take axes that are aligned with the inner box. Consider the parts of the outer box that would be projected on the inner box if you projected either on the x&y, x&z, or y&z planes (i.e. you project on the faces of the inner box). These six pieces of the outer box don’t intersect, and each of them is larger than the face of the inner box on which they project. So this part of the outer box has an area bigger than the total are of the inner box. QED

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

#123

Post by lmkg »

SilasX wrote: post #108
hundt wrote: post #23

Earlier quoted context omitted.

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.

I don't understand: the solution text claims that some permutations are guaranteed to work every time[1]. But you still have to initially land in one of "your" cycles, right? [1] "If it happens that the permutation has no cycles of length greater than 50, this process will work every time and the prisoners will be spared."

You always land in "your" cycle, because you start with the box with your name on it.

All sequences of box-opening that use the method described must eventually cycle, because both box-to-name mappings are 1-to-1. Because it's a cycle, the sequence must eventually lead back to the box you started with. Since you start with the box with your name on it, then whatever cycle you landed it, it definitely contains the box with your name on it, because that box is the one that completes the cycle. The only question is whether the cycle is length-50 or less.

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

#124

Post by czr80 »

adium wrote: post #64
_archon_ wrote: post #56

Earlier quoted context omitted.

There's a discrepancy between the number of visible blues and the number given. Say the person is a blue and doesn't know it. They can count b-1 blues on everyone else. Hearing "r reds, b blues, 1 yellow," he knows he must be either blue or yellow. He doesn't know which. Everyone survives. Edit: had a paren instead of opening quote.

I'm also thinking it would need to be at least a couple hundred people to be classified as a town. Which then the odds of someone subconsciously counting a number that high in their head is unlikely. In a classroom with 30 people right now and I couldn't tell you how many of each gender there are unless I actively try. If that meant certain death, why would I count?

You're being downvoted, which is a bit harsh. However, you are thinking about this as a practical problem, when it is actually a mathematics exercise.

The distinction comes naturally to some people, it's a real struggle for others.

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

#125

Post by joveian »

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

Should work fine if the locked box is sent first...

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

#126

Post by pkroll »

ythl wrote: post #117
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.

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.

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

#127

Post by cousin_it »

pfedak wrote: post #115
cousin_it wrote: post #91

Earlier quoted context omitted.

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.

By projected perimeter I mean the sum of lengths of projections of all edges. I'm not canceling them out or anything. Think of the box as a graph, its projection is another graph that happens to lie on a straight line, but we can measure the sum of its edges regardless.

It's not completely obvious why the projected perimeter of the inner box is bounded by the projected perimeter of the outer box, but it's a statement about one-dimensional segments that's easy enough to check.

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

#128

Post by albinofrenchy »

JoeAltmaier wrote: post #8

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 they did before the statement, otherwise a merciful stranger could say 'The number of blues is less than ' each day, where the big number is more than the population.

Unfortunately that stringent of a definition for non-trivial sort of ruins the problem since in the formulation is the idea that at least one person in the village gets (at least) one number closer to knowing the exact number of blues everyday, and as soon as they know the exact number of blues they are eliminated.

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

#129

Post by pkroll »

It's not in the same vein, but my favorite puzzle is the Monty Hall Problem. Although as is relentlessly pointed out, it's not actually how "Let's Make A Deal" works.

Monty Hall shows you three doors, two have goats behind them, one has a brand new car. While still closed, you pick a door. After you've picked, Monty opens one of the other two doors to show you a goat, and asks if you want to stay with your choice, or choose the other remaining door. What do you do? Stay? Switch? Or it doesn't matter?

For background and spoiler, https://en.wikipedia.org/wiki/Monty_Hall_problem

Edit: Spelling

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

#130

Post by posterboy »

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…

> If the light is on when F gets to the room, they turn the light off, and they increment their counter.

Who is they???

Post reply on HN