Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf] • Hacker News Board

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

#111

Post by CamperBob2 » Sat, May 05, 2018, 10:39 PM UTC

jameshart wrote: post #90

cabaalis wrote: post #71

Earlier quoted context omitted.

I think "What comes next?" is an incomplete question, without any context. "What comes next in the sequence of (blah)?" is a complete question with full context. But that question wouldn't make anybody feel superior. "Identify as many sequences as you can which fit this set of numbers, and tell me the next number in each sequence" is the non-trick actually being asked.

I think the only sane approach is to apply a Kolmogorov-shaded Occam's Razor, and select, from the set of possible sequences which fit the pattern, the one which has the simplest generating function.

That can be tricky in itself, though. 1, 2, 3, 4, .... might be a sequence of positive integers, or it might be a subset of pseudo-random digits emitted by a maximal-length shift register sequence.

Someone recently pointed out to me that if you were designing hardware to (e.g.) refresh all memory locations in a system, or otherwise visit a set of 2^n sequential locations in no particular order, then using a maximal-length shift register of the appropriate width is actually simpler than a 'simple' adder or subtractor. That could be seen as a literal interpretation of Kolmogorov complexity.

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

#112

Post by CamperBob2 » Sat, May 05, 2018, 10:46 PM UTC

johnc1231 wrote: post #88

I always liked the prisoner box question, but I prefer the phrasing where the prisoners are assigned a number and the boxes are numbered. I feel like the "prisoners have to come up with a name to number mapping" step just gets in the way of the interesting part.

I don't understand one assertion that the author makes in the solution, though:

    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.

Obviously that's not true as written, because the first prisoner has odds of 50% no matter what function or algorithm they use to choose the boxes they open. If they fail in their initial guesses, the game stops immediately and everyone dies. What am I missing?

Furthermore, if you simplify the case to two prisoners and two boxes, where each is allowed to open one box, the odds of "success" are clearly only 25%. What happens as the number of prisoners and boxes grows that improves the odds? This isn't a classic Monty Hall variation where the participants have additional options as the game progresses -- it's completely predetermined.

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

#113

Post by fydorm » Sat, May 05, 2018, 10:47 PM UTC

Deestan wrote: post #53

anyfoo wrote: post #37

Earlier quoted context omitted.

Would they be fine? So let's say there are two people with red dots, let's name them Ruth and Rudy. Ruth now knows that "not all dots are blue" (which is equivalent to "there is at least one red dot"). She sees Rudy with the red dot: Fine, here's the person with the red dot. But wait a minute, why is Rudy not killing himself? If Rudy is the only person with a red dot, he should have seen only blue dots... however he…

Given 2 red dots, they would already know that not all dots are blue even before the stranger comes. At their first town meeting, everyone would know "not all dots are blue" and they would know that everyone else knew that information too. Would this mean the colony would self-implode?

If you have a red dot, you only know that there is at least 1 red dot, and you don't know if that one person knows "not all dots are blue". Hence, it's new information when that person doesn't commit suicide.

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

#114

Post by learnstats2 » Sat, May 05, 2018, 10:53 PM UTC

The Dot Town Suicides appears to be incorrect as stated.

Suppose there are 100 residents and 2 blue dots. The stranger tells everyone "there are not 98 blue dots"

This meets the condition of the question's "non-trivial" but the residents can relax: nobody has learned anything new. The proposed induction is broken, in my opinion.

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

#115

Post by fydorm » Sat, May 05, 2018, 10:54 PM UTC

CamperBob2 wrote: post #112

johnc1231 wrote: post #88

I always liked the prisoner box question, but I prefer the phrasing where the prisoners are assigned a number and the boxes are numbered. I feel like the "prisoners have to come up with a name to number mapping" step just gets in the way of the interesting part.

I don't understand one assertion that the author makes in the solution, though: 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. Obviously that's not true as written, because the first prisoner has odds of 50% no matter what function or algorithm they use to choose the boxes they open. If they fail in their initial guesses,…

If it has cycles of 50 or less only, then they're guaranteed to find their own name (they start the cycle on the box corresponding to themselves, so that cycle must contain them). Incidentally, the "first prisoner" might as well be every prisoner, because they aren't allowed to observe each other, communicate, or modify the room.

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

#116

Post by danbruc » Sat, May 05, 2018, 11:49 PM UTC

tomp wrote: post #94

OscarCunningham wrote: post #75

Earlier quoted context omitted.

This problem frustrates me, I'm not quite convinced that it's well defined as written. My first instinct is to say "Based on your knowledge of Alice, assign a probability distribution over the pairs of integers she might pick. Then when one is revealed you should condition on that fact. Then just pick whichever of higher or lower is most likely." The problem setter will object that we have no way of assigning a proba…

I agree that it’s not entirely strictly specified - in particular, there’s no random (uniform) distribution over integers. I guess you could get around this by specifying in in a way you did, or “parametrized” over some parameter, or say “for any distribution” (and mandate a single turn of the game)... Anyways, this is also highly unintuitive for me, so I’m far from certain that the solution below is correct; having…

Does not work according to [1], see followup puzzle 2 and its solution. At least if my interpretation of your proposed solution is correct, i.e. that you fix your threshold number in advance. Not sure if a delayed random choice would help.

[1] https://johncarlosbaez.wordpress.com/2015/07/20/the-game-of-...

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

#117

Post by bsdetector » Sun, May 06, 2018, 12:55 AM UTC

CamperBob2 wrote: post #112

johnc1231 wrote: post #88

I always liked the prisoner box question, but I prefer the phrasing where the prisoners are assigned a number and the boxes are numbered. I feel like the "prisoners have to come up with a name to number mapping" step just gets in the way of the interesting part.

I don't understand one assertion that the author makes in the solution, though: 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. Obviously that's not true as written, because the first prisoner has odds of 50% no matter what function or algorithm they use to choose the boxes they open. If they fail in their initial guesses,…

> Furthermore, if you simplify the case to two prisoners and two boxes, where each is allowed to open one box, the odds of "success" are clearly only 25%.

No it's still 50%, because first person opens box 1 and second person opens box 2. They both either live or die together.

Three people, 2 chances. Each just guessing independently would be 2/3 chance so the chance for all to win is (2/3)^3 or 30%. But if the first person opens box 1 then they will find their name or not (1/3) and if so the second and third opening 2 and 3 are guaranteed to find their name, so 33% total chance.

The basic idea is that you choose boxes in a dependent pattern so that group either all wins or all loses as much as possible. The more people that can win or lose at the same time the better the overall chance for the group.

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

#118

Post by CamperBob2 » Sun, May 06, 2018, 1:07 AM UTC

fydorm wrote: post #115

CamperBob2 wrote: post #112

Earlier quoted context omitted.

I don't understand one assertion that the author makes in the solution, though: 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. Obviously that's not true as written, because the first prisoner has odds of 50% no matter what function or algorithm they use to choose the boxes they open. If they fail in their initial guesses,…

If it has cycles of 50 or less only, then they're guaranteed to find their own name (they start the cycle on the box corresponding to themselves, so that cycle must contain them). Incidentally, the "first prisoner" might as well be every prisoner, because they aren't allowed to observe each other, communicate, or modify the room.

If it has cycles of 50 or less only, then they're guaranteed to find their own name (they start the cycle on the box corresponding to themselves, so that cycle must contain them)

But there are 100 boxes, assigned at random. The prisoners can come up with a mapping function that predetermines which boxes they will open based on their names, but that function will have no relationship to the one (if any) that was used by the warden.

There is no way to guarantee that the first prisoner finds his name, and that seems to be true for all of the others. It must genuinely be a case where I haven't understood the problem correctly.

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

#119

Post by CamperBob2 » Sun, May 06, 2018, 1:09 AM UTC

bsdetector wrote: post #117

CamperBob2 wrote: post #112

Earlier quoted context omitted.

I don't understand one assertion that the author makes in the solution, though: 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. Obviously that's not true as written, because the first prisoner has odds of 50% no matter what function or algorithm they use to choose the boxes they open. If they fail in their initial guesses,…

> Furthermore, if you simplify the case to two prisoners and two boxes, where each is allowed to open one box, the odds of "success" are clearly only 25%. No it's still 50%, because first person opens box 1 and second person opens box 2. They both either live or die together. Three people, 2 chances. Each just guessing independently would be 2/3 chance so the chance for all to win is (2/3)^3 or 30%. But if the first…

No it's still 50%, because first person opens box 1 and second person opens box 2. They both either live or die together.

As the problem is stated, the boxes remain where they are and must be reclosed after being opened. There are no other choices to be made, there's no way to retain or communicate any information about a particular prisoner's actions, and there are no order-dependent aspects to the problem. Everybody sees the same 100 closed boxes and gets to open 50 of them.

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

#120

Post by Avshalom » Sun, May 06, 2018, 1:15 AM UTC

OscarCunningham wrote: post #100

tomp wrote: post #94

Earlier quoted context omitted.

I agree that it’s not entirely strictly specified - in particular, there’s no random (uniform) distribution over integers. I guess you could get around this by specifying in in a way you did, or “parametrized” over some parameter, or say “for any distribution” (and mandate a single turn of the game)... Anyways, this is also highly unintuitive for me, so I’m far from certain that the solution below is correct; having…

I think the "orthodox" answer is that your method wouldn't work, because if Alice picks 10 and 20 and opens 10 first then you have a 0% chance of winning. Instead (they say) you should pick your number at random, so that it has at least some probability of being any given integer. For example you could pick the number n with probability 2^|n|/3. That way no matter which two numbers Alice picks there's always some pro…

It's important to remember that Alice is a perfect random number generator. She certainly isn't going limit her numbers to what can be comfortably written on the paper for instance.

Which is fun because while there are hundreds of puzzles that require people to be able memorize perfect hash functions on the fly or remember the state of a FSM 1000 states ago or be capable of implementing the necessary function required by the axiom of choice for a given situation...

this is the first puzzle I can think of that requires some one to be able to, with perfect randomness select two integers (-∞,∞)