Ingenious Algorithm Riddle: Imposs. Even w/Answer

[Hornbein]

Hardly anyone would think of this solution. I even wonder how anyone would come up with the question. And it is even more amazing that the questioner and solver were not the same person.

 

[Borg]

I'm curious as to how larger or smaller numbers of selected boxes would affect the outcome. Logically, if they could open more boxes, the odds generated by this strategy would increase. Likewise, selecting fewer boxes would decrease their odds. Thoughts?

 

[.Scott]

I'm curious as to how larger or smaller numbers of selected boxes would affect the outcome. Logically, if they could open more boxes, the odds generated by this strategy would increase. Likewise, selecting fewer boxes would decrease their odds. Thoughts?

For a larger number of boxes (>50), the math is easy. Instead of 1 - (1/51 + 1/52 + 1/53 + ... 1/100) if would be 1 - (1/(n+1) + 1/(n+2) + 1/(n+3) + ... 1/100).

For a smaller number of allowed boxes, the arithmetic isn't so simple.

 

[Vanadium 50]

Does this really take watch a 17 minute video plus ads to understand? Or can someone summarize?

 

[pbuk]

Does this really take watch a 17 minute video plus ads to understand? Or can someone summarize?

It's Miltersen's 100 prisoners problem; the solution depends on whether there is a cycle of length > 50 in the arrangement of the boxes.

More information in a less intrusive form can be found by searching for "Miltersen 100 prisoners" (or just Miltersen; I don't think he did anything else as noteworthy).

 

[Borg]

It's an interesting observation that by selecting the box with your number and then always choosing the revealed number, you will eventually reveal your own number. If all of the prisoners use the same technique, their odds of all of them finding their own number is approximately 1/3. This holds for any starting number of prisoners where the number of boxes that can be searched is equal to half the total number of prisoners. For the case of 100 prisoners, randomly selecting boxes results in infinitely small odds of success.

 

[Hornbein]

Does this really take watch a 17 minute video plus ads to understand? Or can someone summarize?

You've got N slips of paper numbered 1 though N. You've got N boxes numbered 1 through N. The papers are randomly assigned to the boxes.

You must do N trials numbered from 1 through N. In each trial, you must find that trial's number in one of the boxes while searching at most N/2 boxes. You can't remember from trial to trial what happened in any previous trial. If even one of these searches fails, you lose. What is the optimal memoryless strategy for winning?

Spoiler

The key insight is that there are cycles in the box/paper pairs. ( I "proved" this with induction.) Go to the box with the trial's number. Get the number in the box. Go to that box. Repeat. The paper with your trial's number will be found before returning to the first box.

Your odds of winning are then approx. equal to the chance that all cycles are of length N/2 or less. (If not there is a small chance you will luck out anyway.) The odds of this are about 1/3.

 

[pbuk]

Spoiler

(If not there is a small chance you will luck out anyway.)

This is not correct.

Spoiler

WLOG consider 6 prisoners with boxes containing [1:2, 2:3, 3:4, 4:1...] (i.e. a cycle of 4). Each of the prisoners 1-4 stops 1 short of the box containing their number.

 

[Hornbein]

This is not correct.

Spoiler

WLOG consider 6 prisoners with boxes containing [1:2, 2:3, 3:4, 4:1...] (i.e. a cycle of 4). Each of the prisoners 1-4 stops 1 short of the box containing their number.

? This is just one of the cases where the prisoners all die. That happens in about 2/3s of the cases.

I was however wrong in saying the prisoners might luck out in an unfavorable situation. The problem is set up specifically to exclude that.

 

[pbuk]

I was however wrong in saying the prisoners might luck out in an unfavorable situation.

Yes, that is what I quoted from your post. I demonstrated that if there is a cycle of length n > 50 then n prisoners must fail so there is no "lucking out" in this case.

 

[Vanadium 50]

I'm curious as to how larger or smaller numbers of selected boxes would affect the outcome.

Assume the number of prisoners varies and they open half the boxes.

If you have one prisoner, the odds of survival are 100%(assuming he gets to open one box). If you have two, it;s 50%. If you ave very many, you have 1 - log(2) or 30.7%. So that's the trend. Variations around that trend depend on the details of "half the boxes:"

You three guys - half of you come with me!

 

[Ibix]

You three guys - half of you come with me!

You can take Smith and Johnson. Smith's a good man, and Johnson's all right.

 

[hutchphd]

Thoughts?

For a smaller number of allowed boxes, the arithmetic isn't so simple.

Why is the arithmetic more complicated? I assume I am missing something obvious.

 

[.Scott]

Why is the arithmetic more complicated? I assume I am missing something obvious.

Yes.
For values greater than 50, you only need to worry about a single oversize loop. You can't have two 51-count loops because there are only 100 boxes. But with smaller values, you can have multiple oversize loops. So dealing with the total sizes and number of "traps" is less straight-forward.