Ingenious Algorithm Riddle: Imposs. Even w/Answer

Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
Sign up Log in
13 replies · 3K views
Hornbein
Gold Member
Messages
4,120
Reaction score
3,281


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.
 
Reply
  • Like
  • Love
  • Informative
Likes   Reactions: DrClaude, FactChecker, jack action and 3 others
Physics news on Phys.org
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?
 
Borg said:
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.
 
Reply
  • Like
Likes   Reactions: Borg
Vanadium 50 said:
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).
 
Reply
  • Like
Likes   Reactions: Vanadium 50
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.
 
Vanadium 50 said:
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?

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.
 
Reply
  • Like
Likes   Reactions: Vanadium 50
Hornbein said:
(If not there is a small chance you will luck out anyway.)
This is not correct.
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.
 
pbuk said:
This is not correct.
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.
 
Last edited:
Reply
  • Like
Likes   Reactions: hutchphd
Hornbein said:
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.
 
Last edited:
Borg said:
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!
 
hutchphd said:
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.
 
Reply
  • Like
Likes   Reactions: hutchphd and pbuk