15 ms·
100 prisoners problem
- dbatten 8y agoI'm confused... "Before the first prisoner enters the room, the prisoners may discuss strategy—but may not communicate once the first prisoner enters to look in the drawers." And, in the example given, "That prisoners 5 to 8 will also find their numbers can also be derived from the information gained by the first three prisoners." There's never any explanation of what happens when a prisoner opens a drawer and finds it empty. In the first example given, what happens when prisoner 5 goes in and there's nothing in drawer 5? The algorithm doesn't seem to account for this. It seems like there's some sort of assumption that the later prisoners are gathering information from the earlier prisoners, but the problem set-up seems to preclude this? They're going into a room so they can't watch each other, the drawers are closed afterwards so they can't derive information from which drawers are open/closed, and they're not allowed to communicate. Am I not following something?
- deleted 8y ago[deleted]
- mabbo 8y agoI think you're right that the statement doesn't make sense- or else we're both not understanding it. From what I can see, no prisoner needs any information beyond knowing their own number. Once they know that, they're just searching the cycle that their number is in to see if it's less than 50-long.
- ajanuary 8y agoThe numbers are left in the drawers once someone finds their number.
- antognini 8y agoThe statement "That prisoners 5 to 8 will also find their numbers can also be derived from the information gained by the first three prisoners" is poorly worded. I think the author intended it to mean the information gained to you, an outside observer trying to prove this statement. There is no transfer of information from one prisoner to the next. Also, when the prisoners find their number they don't remove it. No drawers are ever empty. They just have to open a drawer that contains their number.
- falcor84 8y agoAbsolutely agreed about that sentence being poorly phrased; I've edited that now.
- dbatten 8y agoTwo things: 1) You don't take your number when you find it. I guess my brain assumed "find" meant "find and take with you to prove you found it." Perhaps a better term might be "encounter." 2) Here's a much better explanation (thanks micaeked): http://datagenetics.com/blog/december42014/index.html http://datagenetics.com/blog/december42014/index.html. Essentially, the algorithm works because following numbers to drawers will eventually create a loop (e.g., drawer 2 points to 4 points to 6 points to 2). By starting with the drawer with your number, you're guaranteed to be in a loop with your number. The only question is whether your loop is less than 50 drawers long... Furthermore, this confirms that there IS no transfer of information from previous prisoners in any way.
- chongli 8y agoThe only question is whether your loop is less than 50 drawers long... So then the question is: what proportion of the permutations of 100 numbers contain a cycle greater than 50 vertices long? Is it 30%? The claim made in the Wikipedia article is that the prisoners have around 30% chance of surviving. Edit: looks like that is the case. You can even take the limit of the number of boxes (hence prisoners) to infinity and their probability of survival never drops below 30%! This is an amazing result.
- deleted 8y ago[deleted]
- justadudeama 8y agoCan you explain to me why it is guaranteed you will be in a loop with your number?
- deleted 8y ago[deleted]
- deleted 8y ago[deleted]
- laurentl 8y ago
- deleted 8y ago[deleted]
- deleted 8y ago[deleted]
- niftich 8y agoIf I understand this correctly, this basically uses the drawer's perceived number as an out-of-band signalling mechanism for the algorithm they agreed to follow. Each actor must adhere to the same scheme to address drawers. This means that the drawers must either be uniquely named ("labelled" ahead of time), or have some sort of natural ordering that's algorithmically deterministic (e.g. lexicographic, array index, 2D-position using a previously agreed algorithm like right-then-down). What are some practical uses for this? Distributed hash table traversal using one's own address [1]? [1] http://www.bittorrent.org/beps/bep_0005.html http://www.bittorrent.org/beps/bep_0005.html
- blattimwind 8y ago> What are some practical uses for this? Exercise sheets for discrete mathematics courses.
- IneffablePigeon 8y agoThis "look at it as a permutation problem and follow the disjoint cycles" idea is loosely what rainbow tables are based on (although I think in that case because of the possibility of hash collisions they aren't guaranteed to be disjoint cycles, which requires extra work to solve).
- qntty 8y agoDan Luu has a post about how permutation cycles come up in two algorithms https://danluu.com/sattolo/ https://danluu.com/sattolo/
- micaeked 8y agoSince wikipedia doesn't explain why it works (or maybe I just didn't understand it), I found this explanation much better: http://datagenetics.com/blog/december42014/index.html http://datagenetics.com/blog/december42014/index.html
- dbatten 8y agoThank you. This is a MUCH better resource.
- manojlds 8y agoThis sentence did the trick: > Because the prisoner starts on the box of their own number they are, by definition, on the chain that contains their ticket (there is only one ticket that points to that box).
- jgtrosh 8y agoThat's really the sentence that seems to be wrong, until you see the light shine through the problem.
- dEnigma 8y agoAh yes, that's where I first heard about this problem. Dategenetics is a great blog in general, with lots of interesting content.
- squeakynick 8y agoThanks for the compliment. </blush>
- thaumasiotes 8y agoWikipedia provides exactly the same explanation that your link does: > The prison director's assignment of prisoner numbers to drawers can mathematically be described as a permutation of the numbers 1 to 100. > Every permutation can be decomposed into disjoint cycles, that is, cycles which have no common elements. > In the initial problem, the 100 prisoners are successful if the longest cycle of the permutation has a length of at most 50. Their survival probability is therefore equal to the probability that a random permutation of the numbers 1 to 100 contains no cycle of length greater than 50. What did you think was missing from the Wikipedia article?
- keketi 8y agoDo the prisoners remove their number from the drawer if they find it? It's not clear from the problem statement.
- ajanuary 8y agoThey do not.
- moate 8y agoIf they did, you essentially go back to random choice because of all the broken chains created. "Find" is meant to imply literally "discovering the location of data that correlates to their prisoner number". Real world context implied that prisoners would also take the tickets, but that is not specifically stated.
- edanm 8y agoMy favorite version of this is the one that shows one prisoner to make a single swap of two drawers' contents in order to improve their chances. Surprisingly, this allows for a 100% success rate.
- joncrane 8y agoYeah this is the cool part. If you have a secret agent, he only has to make one change to guarantee success. (Success may already be guaranteed, but by the time the secret agent leaves the room, all prisoners are guaranteed to be safe).
- gowld 8y agoDoe the "hacker" get to see all the contents? Or only 50 (half?) If the hacker needs to break the longest permutation in half (consider the simple permutation x->(x+1), they could ... swap box 0 with box 50, so box 0 points to 51 (->52 .. -> 99 -> 0) and box 50 points to box 1. That makes 2 cycles of size 50, but requires inspecting 50+1 boxes
- pythonaut_16 8y agoThat's an interesting follow up question. What is the minimum number of boxes the hacker/spy/secret agent needs to see to guarantee success?
- deleted 8y ago[deleted]
- flyGuyOnTheSly 8y agoI didn't understand this example... because it seemed like blatant cheating... The prisoners are risking death... The rules are clear... only 50 boxes per prisoner... Why would somebody take the risk of opening 100 boxes? I suppose it's an interesting thought experiment...
- edanm 8y agoIt's a different riddle, not a different solution to the riddle. It's asked differently: given the same setup, except you have one extra person who's the leader, and he's allowed to go in and look at all the boxes, then make one change.
- billysielu 8y agoRight, so picking a box at random and following the chain would be bad because you could get back to where you started having not found your number. Starting with your own numbered box is your defense against this because to go back to where you started you would have to have found your number.
- daxfohl 8y agoThis was my aha moment. I was thinking, the solution presented seemed not only invalid but ill-defined, as you could hit a cycle and still have picks left. With this, it totally makes sense why it works: if there are disjoint cycles, this strategy guarantees that each prisoner is on its own cycle. And I guess the math works out that in unidirected graphs of 100 nodes, 30% of them contain only disjoint cycles of 50 or fewer nodes.
- sigotirandolas 8y agoBecause of the way that the problem is set up (each of the 100 numbers is in one of the 100 lockers), it can always be written as a list of disjoint cycles (mathematically: every permutation can be written as a product of disjoint cycles). So, by starting in your own locker, you will eventually end up finding your own number. The only constraint is that everyone has to do it in 50 tries or less, i.e. there's no cycle of length >50.
- ddtaylor 8y agoNot that it's fair to ask you this, but how would we model the probability of picking chains at random? I would assume it's much better than the (1/2)^(100) approach of picking random each time.
- flyGuyOnTheSly 8y ago>I would assume it's much better than the (1/2)^(100) approach of picking random each time. You can assume whatever you wish, but the calculated proof is right there in your statement.
- CydeWeys 8y agoI wrote up a Python framework to play around with a different 100 prisoners problem here: https://github.com/CydeWeys/hundred_prisoners/tree/master/prisoners https://github.com/CydeWeys/hundred_prisoners/tree/master/pr... People might find it interesting to play around with implementing the solution in code.
- jwilk 8y agoLet's make the game harder by not letting the prisoners see what's inside the opened drawers. Is it hopeless now?
- jrq 8y agoYes
- majewsky 8y agoThat's just a game of chance. The point of a skill game, even one that involves randomness, is that information you get can influence your actions. If you cannot look inside the drawers, you do not gain any information about the particular setup and thus cannot execute anything that would resemble a strategy.
- dmurray 8y agoThey can still do slightly better than chance by ensuring their guesses have the right amount of overlaps. For example, if there were only two prisoners, the right strategy would be for one to pick box 1 and the other one to pick box 2, improving their odds of survival from 25% to 50%. I suspect the chances are still negligible for 100 prisoners though.
- deleted 8y ago[deleted]
- peeters 8y ago> I suspect the chances are still negligible for 100 prisoners though. I think from a probabilistic standpoint, they're equivalent as n increases. Think of it as the inverse; what's the probability each box is checked by its owner? Pb = Nb / N, or number of people that checked that box divided by number of people total. If there is perfect, premeditated overlap, then Nb / N is exactly 50/100, so we get the "(1/2) ^ 100" that was already cited in the article. If prisoners choose randomly though, the expected value of Nb is still 50 though. You've maximized Nb in practice, but not really in theory.
- pramodzion 8y agoHN post from 2010 : https://news.ycombinator.com/item?id=1891212 https://news.ycombinator.com/item?id=1891212
- martininmelb 8y agoWhat does the prisoner do if she gets to, for example, box 40 and there is a 40 in the box? [edit] I reread the explanation and get it now. Only 1 prisoner (40) will actually get to open box 40. I was trying to think of this from the point of view of implementing it in code. I guess the cycle stops when a prisoner finds their own number or reaches 50 attempts.
- jakear 8y agoWhy would they have gone to box 40 in the first place had they not gotten a number 40 from elsewhere?
- twentythree 8y agoThe third variant of the problem (where one prisoner is allowed to make one change, which can guarantee that every prisoner survives) is the one I heard first; I like that problem because it seems even more counter-intuitive, but also makes it easier to understand why it works.
- DimitarIbra9 8y agowhy is this article in frontpage? somebody is asked for this in a interview?
- utopcell 8y agoSay you have 10 players in a row. You number each player by its position in the row: 1, 2, 3, .., 10. You then write the players' names on 10 pieces of paper, and you randomly place the papers in 10 boxes. You place exactly one paper in each of the boxes. The boxes are also numbered from 1 to 10. You allow each player to look into half of the boxes. Each player can choose which boxes to look into. The player "wins" if they find a paper with their number written on it. But they can't tell anyone if they won or lost, what they saw in the boxes, or which boxes they picked. The problem then, is the following: Which boxes should each player look into, such that the chance of all of them "winning" at the same time is as high as possible. For example, one way to put the 10 numbers in the 10 boxes is: Box 1: 10 Box 2: 9 Box 3: 8 Box 4: 4 Box 5: 6 Box 6: 5 Box 7: 7 Box 8: 3 Box 9: 2 Box 10: 1 The ordering of the numbers in the boxes is a permutation of the 10 numbers. We know that there are 10! possible ways to place the numbers in the boxes. Now, consider the following strategy that player X can use to open his 5 boxes. He first opens the box numbered X. If he sees his number in it, then he wins. Otherwise, he saw a different number Y. He then opens the box numbered Y. If he finds his number, he wins. Otherwise, he continues until he has opened the 5 boxes he is allowed to open. If the player was allowed to open as many boxes as he likes, they he would always win. That is because he would either find his number in a box, or continue opening boxes he hasn't opened before. Why is this true ? Well, let's say it isn't, and that he opens boxes 3 -> 2 -> 5 -> 7 -> 5. But that cannot happen: The first time he opened box 5 was because he saw the number 5 in box 2. And if he had to see box 5 again, this means that box 7 also had the number 5 in it. In fact, the only way player X could go back to a box he has seen, is when he finds his number (X) that will lead him back to the first box he opened. Now, we know that a player "wins" if he finds his number before opening more than 5 boxes. Or, put it differently, if the loop he follows has length at most 5. In the example above, player 2 would open box 2, which would lead him to box 9, which contains number 2, forming a loop of length 2. So, when do all players "win" at the same time ? When there does not exist a loop that has length 6 or more. Or more specifically, there is no loop of length 6, or 7, or 8, or 9, or 10. So: P_win = 1 - P_loop(6) - P_loop(7) - P_loop(8) - P_loop(9) - P_loop(10). We can show [1] that P_loop(k) = 1/k, when k > 5. We need the loop to be larger than 5 because in this case, there can only be one such loop on the permutation. But then P_win would be 1 - 1/6 - 1/7 - 1/8 - 1/9 - 1/10 or ~35.4%. In general, if we have N players and N boxes then P_win would be: P_win = 1 - Sum[k=n/2+1 .. n]P_loop(k) or P_win = 1 - ( Sum[k=1 .. N]P_loop(k) - Sum[k=1 .. N/2]P_loop(k) ) or P_win ~= 1 - ( ln(N) - ln(N/2) ) > ~30% (each sum is a harmonic series sum.) [1] Why is P_loop(k) = 1/k when k > N/2 though ? Let's say you have numbers 1, 2, .., k. All permutations of them are k!. How many of those k! permutations form a loop ? Well, at the first position, you can place any number other than '1', so you have (k-1) choices. Say you placed number Z at position 1. Then at position Z, you can't place '1' and you can't place 'Z', so you are left with (k-2) choices. In the last position, you have to place number '1' to close the loop, so you have no choice. So, you have (k-1)(k-2)(k-3)...1 ways to form a loop, or (k-1)!. Therefore, with a little bit of squinting, we can see that the probability that a random permutation has a loop on it of length exactly k is (k-1)!/k!, or 1/k. We can formalize this argument as follows: There are (N choose k) ways to pick the k places on the permutation where there exists a cycle. There are (k-1)! valid ways to form a cycle on these k places. There are (N-k)! ways to arrange the remaining elements on the permutation. There are N! permutations, Therefore, P_loop(k, N) = (N choose k)(N-k)!(k-1)! / N! = N! / k! / (N-k)! * (N-k)! * (k-1)! / N! = 1/k
- engnr567 8y agoOne key thing about the result is that it doesn't mean that the probability of survival is 30%. The prison director can choose an arrangement such that the strategy is guaranteed to fail. If the prison director is intelligent and after your life, you are infinitely more likely to survive by opening boxes randomly.
- zwkrt 8y agoThe prisoners in the game can collude before the game begins, so they can create their own ordering on the fly. This cannot be overcome by the warden.
- deleted 8y ago[deleted]
- contoraria 8y agoI still doubt the Monty Hall problem (mentioned in the wiki-article). I understand the reasoning, summing the probability tree, but there are two ways to build the probability tree, with the step of reveal or without. Since the player doesn't know that step, why would it be part of the tree? Because we know the setup a priori, in a way. I'm assuming the bigger tree is still incomplete. More levels can be inserted, reflecting the reasoning of the a priori knowledge. I assume the supposed advantage would thus prove to be imaginary. Or in simpler terms: Normally the tree would have the sequence in the following order: box distribution, choose a box, reveal one empty box, switch choice or don't. However, if you are predetermined to switch, then the order would be changed to switch before the reveal. Thereby, the reveal is irrelevant to the result of switching and the probabilities are equal again.
- contoraria 8y agoPS: of course you can't switch before the game maker reveals a box. But isn't that immaterial? In one of three cases, your first choice is correct. Therefore, in two of three cases, the first choice is incorrect ... so switching should be correct in those two.
- taejo 8y ago>However, if you are predetermined to switch, then the order would be changed to switch before the reveal. Thereby, the reveal is irrelevant to the result of switching and the probabilities are equal again. Before the reveal, you don't know which box to switch to. Monty knows which boxes are empty, and he gives you partial information about that by revealing one of them.
- iak8god 8y agoThe best way to become convinced of Monty Hall may be to grab a buddy and some playing cards, and run a simulation. 30 rounds or so should be convincing.
- not_kurt_godel 8y agoI feel similarly about Monty Hall. I literally just made a spreadsheet of all the possible outcomes, and sure enough, switching leads to winning 2/3 of the time. Even though I can see the indisputable data in front of my eyes, my brain just won't fully accept it. Looking at it, I realized an interesting little wrinkle that I think might have to do with the problem's psychological quirkiness in some way I can't fully articulate: When you stay you win 1/3 of the time. When you switch, you win 2/3 of the time. BUT if you randomly pick between staying and switching, you win 50% of the time because (1/2)(1/3) + (1/2)(2/3) = 1/6 + 2/6 = 3/6. There is a correct-ish-ness to the intuitive answer of 50%...it's just not...actually correct.
- travismay1 8y agoWell, this led me on a bit of a rabbit trail. I made a python script that illustrates the solution to this problem in action. https://gist.github.com/travismay1/8d80fe345786b1d0e93fee8127df53b5 https://gist.github.com/travismay1/8d80fe345786b1d0e93fee812...
- mkstowegnv 8y agoAt some intuitive level this problem reminded me of other very different puzzles like [1] and prompted me to wonder if as a general rule the best tactic when one is faced by a riddle that appears impossible, is to try to think of solutions that involve self reference. It also makes me wonder if the brain at a basal unconscious level uses something analogous to the linked list like solution described here to quickly explore permutation space. 1 https://en.m.wikipedia.org/wiki/Knights_and_Knaves https://en.m.wikipedia.org/wiki/Knights_and_Knaves
- Myrmornis 8y agoMany mathematical-minded people look at this problem and conclude that the maximum probability of freedom is close to (1/2)^50. But that's absurdly wrong. They're out by a factor of 10^14 !!! So, are there any important problems in computer science / software engineering contexts that have this form? If so, they may have speed-ups of several orders of magnitude that mathematically and algorithmically-minded people might completely miss?