Misplaced Pages

Talk:100 prisoners problem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

This is an old revision of this page, as edited by Anita5192 (talk | contribs) at 17:23, 11 February 2020 (Removed some unnecessary blank lines.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Revision as of 17:23, 11 February 2020 by Anita5192 (talk | contribs) (Removed some unnecessary blank lines.)(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)
WikiProject iconMathematics C‑class Low‑priority
WikiProject iconThis article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Misplaced Pages. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
CThis article has been rated as C-class on Misplaced Pages's content assessment scale.
LowThis article has been rated as Low-priority on the project's priority scale.
This article contains a translation of Problem der 100 Gefangenen from de.wikipedia.
A fact from 100 prisoners problem appeared on Misplaced Pages's Main Page in the Did you know column on 14 July 2014 (check views). The text of the entry was as follows: A record of the entry may be seen at Misplaced Pages:Recent additions/2014/July. The nomination discussion and review may be seen at Template:Did you know nominations/100 prisoners problem.
Misplaced Pages

Creation request

The following request was added some time ago to Misplaced Pages:Requested articles/Mathematics#Recreational mathematics, which I have now moved here:

This source might be added to the article if it adds anything. Frieda Beamy (talk) 17:52, 30 June 2014 (UTC)

Thanks for the notice, but the article has better sources. Best wishes, --Quartl (talk) 18:07, 30 June 2014 (UTC)

Example

The first example is as follows:

The prison director has distributed the prisoners' numbers into the drawers in the following fashion

number of drawer   1     2     3     4     5     6     7     8  
number of prisoner 7 4 6 8 1 3 5 2

The prisoners now act as follows:

  • Prisoner 1 first opens drawer 1 and finds number 7. Then he opens drawer 7 and finds number 5. Then he opens drawer 5 where he finds his own number and is successful.
  • Prisoner 2 opens drawers 2, 4, and 8 in this order. In the last drawer he finds his own number 2.
  • Prisoner 3 opens drawers 3 and 6, where he finds his own number.
  • Prisoner 4 opens drawers 4, 8, and 2 where he finds his own number. Actually, this was already known to prisoner 1.
  • That prisoners 5 to 8 will also find their numbers can also be derived from the information gained by the first three prisoners.

Unless I'm missing something, Prisoner 4 is a maverick, Prisoner 1 is psychic, and Prisoner 2 is forgetful:

1)"Prisoner 4 opens drawer 4, 8 and then 2." Prisoner 2 has already indicated that number 4 is in drawer 2 so Prisoner 4 could have just opened that directly. Why does Prisoner 4 open two more drawers? Drawer 4 we already know contains the number 8 and drawer 8 is already open/empty/out of the game as Prisoner 2 found their number in it. If all the combinations were not known there would be an advantage to not going directly to your number, as opening your allotment (not the allotment - 1 as Prisoner 4 does here) would provide more information for the subsequent prisoners, but in this case all the drawer/number combinations have already been identified. Poor Prisoner 4.

2)"Actually, this was already known to prisoner 1." Prisoner 1 opened drawers 1,7, and 5 so how would they have known that drawer 2 contained number 4? "Prisoner 2 opens drawers 2, 4, and 8 in this order." So it was Prisoner 2 not Prisoner 1 that knew drawer 2 contained number 4.

I am as mathematical as I am musical (Lalahalah-sqreeKK-La), so I'm quite prepared to be told I haven't understood, but in that case the examples could do with fleshing out. Belle (talk) 08:05, 1 July 2014 (UTC)

The prisoners are not allowed to communicate with each other. Maybe the phrase "was already known" is misleading, I'll reformulate it. Best wishes, --Quartl (talk) 08:11, 1 July 2014 (UTC)
Sorry, it seems I mixed up prisoners 1 and 2. Thanks for pointing this out. --Quartl (talk) 08:16, 1 July 2014 (UTC)
Ahhhhhhh, I see. I thought the prisoners were observing the previous attempts...You should probably remove "Actually, this could have been derived from the information gained by prisoner 2", because the prisoners could not have derived it and the observer can only derive it by altering the parameters of the problem. It's confusing for mathematical dummies like me and probably not helpful for maths types. Belle (talk) 08:31, 1 July 2014 (UTC)
At this point, a change of perspective from the prisoners' view to an outsider's view is made. Actually, this change of perspective is intentional, since we don't want to carry out the same computations again and again. Do you think it would be more instructive to state all opened drawers for all prisoners first and afterwards argue that an outside observer would have known that the prisoners will survive already after the third one? Best wishes, --Quartl (talk) 08:49, 1 July 2014 (UTC)
I made the change of perspective clearer in the article. --Quartl (talk) 09:17, 1 July 2014 (UTC)
Yes, that's better. (Now I've re-read it, it is clear that the remaining prisoners do not see the previous attempts. It was early, I hadn't had coffee. Excuses, excuses). Belle (talk) 09:24, 1 July 2014 (UTC)
Don't worry, your remarks were certainly helpful. It is a difficult subject. Best wishes, --Quartl (talk) 09:37, 1 July 2014 (UTC)

New section on individual probability of success.

Does following this strategy alter the individual's probability of finding a randomly placed number? If you may open 50% of the drawers randomly, then you have a 50% chance of success. If you follow chains, and the probability that ALL chains are shorter than 50% of the total is 31% (and thus a 31% probability that ALL prisoners will be successful in finding their number is 31%), then is the probability that a chain longer than 50% of the drawers exists AND you choose that chain such that the probability for the individual finding their number still 50% ?

Thecheckboard (talk) 13:20, 16 December 2014 (UTC)

The success probability of an individual prisoner using the cycle-following strategy is still 50%. This probability can be derived as follows:
  • If the length of the longest cycle is at most 50, then the success probability is 100%.
  • If the length of the longest cycle is exactly 51, then the success probability is 49%.
  • If the length of the longest cycle is exactly 52, then the success probability is 48%.
  • ...
  • If the length of the longest cycle is exactly 99, then the success probability is 1%.
  • If the length of the longest cycle is exactly 100, then the success probability is 0%.
Therefore, the total success probability of an individual prisoner using the cycle-following strategy is
( 1 − H 100 + H 50 ) + ∑ n = 1 50 1 50 + n ⋅ 50 − n 100 = ( 1 − H 100 + H 50 ) + ( H 100 − H 50 − 1 2 ) = 1 2 {\displaystyle (1-H_{100}+H_{50})+\sum _{n=1}^{50}{\frac {1}{50+n}}\cdot {\frac {50-n}{100}}=(1-H_{100}+H_{50})+(H_{100}-H_{50}-{\tfrac {1}{2}})={\tfrac {1}{2}}}
Most probably there is an easier way to compute this probability, but that is the direct approach :-). Best wishes, --Quartl (talk) 17:30, 16 December 2014 (UTC)

Requested move 7 March 2018

The following is a closed discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a move review. No further edits should be made to this section.

The result of the move request was: no consensus to move the page at this time, per the discussion below. Dekimasuよ! 02:49, 20 March 2018 (UTC)

100 prisoners problem → Locker Puzzle – There are a lot of problems about 100 prisoners, there is no evidence that "100_prisoners_problem" would be recognized as this problem. "Locker Puzzle" is more recognized name. It looks like in all references where this problem is referred by a name it referred by "Locker Puzzle" starting from Curtin and Warshauer's paper Alexei Kopylov (talk) 23:37, 7 March 2018 (UTC)--Relisting. —usernamekiran(talk) 19:06, 14 March 2018 (UTC)

"Locker puzzle" isn't any less ambiguous. The article subject is referred to as "100 prisoners problem" in the secondary literature by very respectable authors, such as Flajolet/Sedgewick and Stanley, which should be enough to justify the title. 2A01:598:A005:BBC9:1:1:580A:EC48 (talk) 14:48, 10 March 2018 (UTC)
The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page or in a move review. No further edits should be made to this section.
Categories: