MATHS EXPLORATIONApplication of theHundred Prisoners Problem CONTENT CONTENT.
2 INTRODUCTION.. 3 THE HUNDRED PRISONERS PROBLEM.. 3 THE “GET ACQUAINTED” GAME. 4 SOLVING THE PROBLEM.. 4 RANDOMLY.
4 CIRCULARLY. 5 Permutations. 6 PERSONAL EXPERIMENT. 7 RESULTS. 9 THE PROBABILITY OF OCCURRENCE OF CHAIN LONGER THAN 5. 10 CONCLUSION..
12 BIBLIOGRAPHY. 12 INTRODUCTIONDuring the summerholidays I am usually a counsellor at a summer camp. Not all counsellors knoweach other beforehand and that is the reason why some meetings are organized inorder for them to get to know each other. I am usually responsible for some”get acquainted” games, but since I find them all over-used, I wanted to comeup with something unique. While searching onthe internet for ideas, I unintentionally also encountered the HundredPrisoners problem. THE HUNDRED PRISONERS PROBLEMThis problem’smost famous version was proposed by Philippe Flajoret and Robert Sedgewick in2009.
The problem goes as followed:”A hundredprisoners, each uniquely identified by a number between 1 and 100, have beensentenced to death. The director of the prison gives them a last chance. He hasa cabinet with 100 drawers (numbered 1 to 100). In each, he’ll place at randoma card with a prisoner’s number (all numbers different). Prisoners will beallowed to enter the room one after the other and open, then close again, 50drawers of their own choosing, but will not in any way be allowed tocommunicate with one another afterwards. The goal of each prisoner is to locatethe drawer that contains his own number. If all prisoners succeed, then theywill all be spared; if at least one fails, they will all be executed.
There aretwo mathematicians among the prisoners. The first one, a pessimist, declaresthat their overall chances of success are only of the order of . The second one, acombinatorialist, claims he has a strategy for the prisoners, which has agreater than 30% chance of success.” (Flajoret and Sedgewick, 2009)They both areright, but combinatorialist’s version is the most optimal for success. It givesprisoners a 31.2% chance of survival.
(Flajoret and Sedgewick, 2009) When I first readabout this problem, I found it very artificial, as I could not imagine areal-life situation in which something similar could really happen. But later,I actually found myself thinking about making my “get acquainted” game a bitmore mathematical by incorporating the Hundred Prisoners Problem into it. THE “GET ACQUAINTED” GAMEThe “getacquainted” game was imagined to be based on two groups of 10 counsellors, eachof them having been randomly assigned numbers from 1 to 10 and then the counsellorsfrom group A would need to find their pair (person with the same number) fromthe opposite group – they would approach one group B counsellor, they would introducethemselves and tell each other their numbers. If numbers were the same, theywould be successful, but if they were not, the group A counsellor would need tostep up to another group B counsellor. He could address maximum of 5 counsellors.If he found his pair, he would succeed, but if he did not, he would be out ofthe game. As this was a “get acquainted” game, I wanted them all to besuccessful and meet their assigned pairs, so I asked myself how could I maximize the chances of all thecounsellors to succeed. SOLVINGTHE PROBLEMI first weighedthe adequacy of randomly addressing group B counsellors.
RANDOMLYIf only one group A counsellor tries to find his pairand he does it by randomly addressing group B counsellors, he has 50% chance ofsucceeding, since there are 10 group B counsellors and he can only address 5 ofthem:If two Acounsellors look for their pairs randomly, the chances for each of them will be50%; therefore, chances for both of them to succeed is 25%:If 10 counsellorstry this, their chances for success are:As these are small chances, I tried to research other ways of findingpairs, which would give better chances for everyone’s success.CIRCULARLY I imagined 10group B counsellors in a line, each of them standing behind their consecutive number.Each one also possesses ticket with its own number written on it.An example of thesituation for easier understanding:Figure 1: Figure graphically presenting the firstsituation Position number of group A counsellor 1 2 3 4 5 6 7 8 9 10 Ticket number 8 5 3 9 10 1 2 6 4 7 Table 1:Table representing the first situation If a close look atthe situation is taken, it is possible to notice that each counsellor eitherhas the same position number and ticket number (as in the case of 3), or theypossess tickets which are not the same as their position numbers. In the lattercases, ticket numbers point to other positions. For example, the counselloron the first position has number 8 à position 8 has number 6 à and 6 has number 1. After that, this circlerepeats all over again.The 2ndposition has number 5 à 5thhas number 10 à 10thhas number 7 à 7thhas number 2 and so on.
Because ticket numbersare all distinct, there is only one person containing a ticket that is pointingto one other specific position. With that said, itis possible to notice that counsellors at different positions can form somecircles according to their positions and numbers they are containing. Circles in this specificexample are: PermutationsThe occurrence ofcircles can also be considered from a mathematical point of view by usingpermutations, since they are bijective transformations, which transform fromset A into set A1. The upper examplecould be written as a permutation: Circular form: A permutation ? forms4 separate cycles. Bracketsin circular form of permutations give obvious illustration of how many and howlong the cycles are in permutations. If one would liketo find a cycle in which specific number is situated, it would be the mostoptimal for him to enter the appropriate cycle at some point and then progressto the counsellors to which tickets point. If one had number 5 and enter thecycle of the counsellor in the first position, one would never reach personpossessing number 5, because cycles are separated, disabling proceeding fromone to the other. But if one entered cycle with counsellor on a fifth position,he would at some point as well reach a person possessing the sought-after ticketnumber.
Therefore, itwould be the best for a counsellor not to look for his number randomly, but tostart at the standing point with the same number, because this would alreadyguarantee that he is in the right cycle. The only thing he needs in this caseis moving in the way of permutation cycle, which would (after some steps) leadhim to the counsellor with the same ticket number. This would be thebest strategy for enhancing the number of successfully met participants in a’get acquainted’ game. PERSONALEXPERIMENTThe problem’sartificiality still worried me and I was not sure if it will truly be possibleto carry the game out in a real life situation. Therefore, I decided topre-test the procedure by conducting a similar problem with my classmates.The example wassimplified by conducting a pre-test on 10 students only. They were all Math SLstudents. I chose them because I knew that their level of mathematical knowledge is similar tomine, so I could understand their reasoning easier and prepare appropriateexplanations.
First of all, 10 boxes were sorted in theline and written their consecutive numbers on the top of them. Inside, theywere put tickets with numbers from 1 to 10. Then, participants were assignednumbers from 1 to 10 and presented them their task: they were asked to individuallyapproach the boxes and try to find their number in the boxes by opening up to 5boxes each. After that, they were not allowed to communicate with one another. I also explicitly stressed that I want them all tosucceed, so they needed to come up with the strategy that would be the mostoptimal for their success.
The boxes were put in the following way: Position of the box 1 2 3 4 5 6 7 8 9 10 Number inside the box 8 5 3 9 10 1 2 6 4 7 Table 2:Table representing the first experimental situationThe tickets were not allocated randomly, but I alwayschose them with thought, so that manipulating variables enabled easierdetermination, in which cases the chance of success is the greatest. Even though participants were told to find the beststrategy, they did not find any and only approached the problem by guessing theboxes randomly. When they all completed the search, the results showed thatonly 6 out of 10 students succeeded. Then, they wereexplained the permutations. And after that, participants were exposed to the second condition.
They were onceagain challenged to use the best strategy and they approached the problem byeach person starting at the box with the same number as his ticket number. Tofind out the trends, they were asked to do this in a few differentexamples/permutations: a) Box position number 1 2 3 4 5 6 7 8 9 10 Hidden ticket number 1 3 8 6 7 4 9 10 5 2 Table 3:Table representing the second experimental situationb) Box position number 1 2 3 4 5 6 7 8 9 10 Hidden ticket number 2 5 7 9 4 10 8 3 1 6 Table 4:Table representing the third experimental situationc) Box position number 1 2 3 4 5 6 7 8 9 10 Hidden ticket number 7 10 2 1 3 4 6 9 5 8 Table 5:Table representing the fourth experimental situationd) Box position number 1 2 3 4 5 6 7 8 9 10 Hidden ticket number 10 5 8 2 6 1 9 3 4 7 Table 6:Table representing the fifth experimental situatione) Box position number 1 2 3 4 5 6 7 8 9 10 Hidden ticket number 3 2 9 7 8 5 1 4 10 6 Table 7:Table representing the sixth experimental situation RESULTS Circular form of permutation Length of cycles units Successful students Unsuccessful students Percentage of successful students Students were randomly opening the boxes, because they did not know how to approach the problem otherwise. 1, 2, 3 and 4 6 4 60% On this point, students were informed about permutations and how transformations actually form apparent cycles. 1, 2, 3 and 4 10 0 100% 2, 3 and 5 10 0 100% 4 and 6 4 6 40% 2 and 8 2 8 20% 1 and 9 1 9 10% Table 8:Table presenting the students’ successfulness according to the chosenpermutationsResults provided evidence that when students wereinformed about permutations, they more easily found their numbers – in twocases they even all succeeded! As it was aimed to prepare a game in whicheveryone would succeed, I was especially interested in the cases in which 100%of students succeeded. The two cases only shared one feature: they both hadcycles no more than 5 units long. It was also possible to notice that eventhough the participants used the best strategy in all cases, the percentage ofsuccessful students declined as the longest cycle in a permutation becamelonger.This occurred because the number of students thateach person could address was limited on 5. If permutation cycle was longerthan that, students with numbers in this cycle could not reach the boxes withtheir numbers.
Students can for sure win only if their numbers are inpermutations in which the length of the longest cycle do not exceed 5. If numbers areassigned randomly to the boxes, there can only be one cycle longer than 5. Ifthere is for example one permutation with the cycle length of 6, there onlyremain 4 numbers that are not used up. Therefore, it is possible to calculatethe chances of all group A counsellors’ success by only calculating the chancesof occurrence of a permutation longer than 5. THEPROBABILITY OF OCCURRENCE OF CHAIN LONGER THAN 5Chains that aretoo long are all chains of length from 6 to 10 tickets. Chain cannot be longer than 10, because each number is used only once.
The boxes arepositioned forming a straight line. Tickets can be allocated in this line in10! ways, because there are 10 boxes, but for the length of the chain l,the boxes can be arranged in ways. GENERAL FORMULA: Therefore, one specificticket number can only be allocated in 10 different ways, because it can beallotted to 10 differently positioned boxes; two inside numbers can beallocated in 45 different ways, three inside numbers can be allocated in 360ways and so on.If the ticketswould permute linearly, the number of ways in which tickets could permute wouldbe But because the chains of tickets in our caseare circular, 1 is subtracted. Therefore, the number of ways in which ticketscan be arranged in circles is: The remainingtickets can be arranged in different ways, but they are not greater than5.The abovereduction of fraction gives a solution of , with representing all the possibilities, and representing the share of them which are withthe length of l.
Therefore, probability that there exists a chain of length l is just . For thecalculation of possibility of every student’s success, we therefore need tocalculate the chances of occurrence of chains of each different length, from 6to 10 units. This is prettyhigh percentage, but anyway low enough that it cannot guarantee that allparticipants of my ‘get acquainted’ game will be successful. If I wanted themall to succeed, I would have to make permutations in which the longest cyclewould be no longer than 5. I should not allot numbers randomly, but withthought, so that no permutation has a cycle longer than 5. CONCLUSIONI first thoughtthat simplifying the problem will impede my experiment, but it actually turnedout to be beneficial, because it enabled me to more easily examine how chancesof all participants succeeding could be maximized.
From the analysisof the conducted experiment, it was possible to conclude that chances of allcounsellors to succeed are maximized by using permutations and permutationcycles. However, random settlement of the tickets would give only 35.4% ofchances that they all succeed. Therefore, in order for 100% of counsellors tosucceed, tickets should be thoughtfully distributed among group A and group Bcounsellors, so that no cycle of the formed permutation is longer than five.
By conducting anexperiment, it was also discovered that performing a mathematical “getacquainted” game would not be as convenient as it was first believed. Because”get acquainted” games are thought to be fun, but the involvement ofmathematics could be unpleasant for the ones who are not that confident intheir mathematics, it would be better to conduct it for example as a game onMath Camps, where there are students who are all interested in mathematics.Otherwise, the Hundred Prisoners Problem was found out to be difficultlyapplied to the real world, however, it would be appropriate as a mathematicalriddle for high school students.