MATHS EXPLORATION

Application of the

Hundred 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

INTRODUCTION

During the summer

holidays I am usually a counsellor at a summer camp. Not all counsellors know

each other beforehand and that is the reason why some meetings are organized in

order 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 come

up with something unique.

While searching on

the internet for ideas, I unintentionally also encountered the Hundred

Prisoners problem.

THE HUNDRED PRISONERS PROBLEM

This problem’s

most famous version was proposed by Philippe Flajoret and Robert Sedgewick in

2009. The problem goes as followed:

“A hundred

prisoners, each uniquely identified by a number between 1 and 100, have been

sentenced to death. The director of the prison gives them a last chance. He has

a cabinet with 100 drawers (numbered 1 to 100). In each, he’ll place at random

a card with a prisoner’s number (all numbers different). Prisoners will be

allowed to enter the room one after the other and open, then close again, 50

drawers of their own choosing, but will not in any way be allowed to

communicate with one another afterwards. The goal of each prisoner is to locate

the drawer that contains his own number. If all prisoners succeed, then they

will all be spared; if at least one fails, they will all be executed. There are

two mathematicians among the prisoners. The first one, a pessimist, declares

that their overall chances of success are only of the order of

. The second one, a

combinatorialist, claims he has a strategy for the prisoners, which has a

greater than 30% chance of success.” (Flajoret and Sedgewick, 2009)

They both are

right, but combinatorialist’s version is the most optimal for success. It gives

prisoners a 31.2% chance of survival. (Flajoret and Sedgewick, 2009)

When I first read

about this problem, I found it very artificial, as I could not imagine a

real-life situation in which something similar could really happen. But later,

I actually found myself thinking about making my “get acquainted” game a bit

more mathematical by incorporating the Hundred Prisoners Problem into it.

THE “GET ACQUAINTED” GAME

The “get

acquainted” game was imagined to be based on two groups of 10 counsellors, each

of them having been randomly assigned numbers from 1 to 10 and then the counsellors

from group A would need to find their pair (person with the same number) from

the opposite group – they would approach one group B counsellor, they would introduce

themselves and tell each other their numbers. If numbers were the same, they

would be successful, but if they were not, the group A counsellor would need to

step 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 of

the game. As this was a “get acquainted” game, I wanted them all to be

successful and meet their assigned pairs, so I asked myself how could I maximize the chances of all the

counsellors to succeed.

SOLVING

THE PROBLEM

I first weighed

the adequacy of randomly addressing group B counsellors.

RANDOMLY

If only one group A counsellor tries to find his pair

and he does it by randomly addressing group B counsellors, he has 50% chance of

succeeding, since there are 10 group B counsellors and he can only address 5 of

them:

If two A

counsellors look for their pairs randomly, the chances for each of them will be

50%; therefore, chances for both of them to succeed is 25%:

If 10 counsellors

try this, their chances for success are:

As these are small chances, I tried to research other ways of finding

pairs, which would give better chances for everyone’s success.

CIRCULARLY

I imagined 10

group 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 the

situation for easier understanding:

Figure 1: Figure graphically presenting the first

situation

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 at

the situation is taken, it is possible to notice that each counsellor either

has the same position number and ticket number (as in the case of 3), or they

possess tickets which are not the same as their position numbers. In the latter

cases, ticket numbers point to other positions.

For example, the counsellor

on the first position has number 8 à position 8 has number 6 à and 6 has number 1. After that, this circle

repeats all over again.

The 2nd

position has number 5 à 5th

has number 10 à 10th

has number 7 à 7th

has number 2 and so on.

Because ticket numbers

are all distinct, there is only one person containing a ticket that is pointing

to one other specific position.

With that said, it

is possible to notice that counsellors at different positions can form some

circles according to their positions and numbers they are containing.

Circles in this specific

example are:

Permutations

The occurrence of

circles can also be considered from a mathematical point of view by using

permutations, since they are bijective transformations, which transform from

set A into set A1.

The upper example

could be written as a permutation:

Circular form:

A permutation ? forms

4 separate cycles. Brackets

in circular form of permutations give obvious illustration of how many and how

long the cycles are in permutations.

If one would like

to find a cycle in which specific number is situated, it would be the most

optimal for him to enter the appropriate cycle at some point and then progress

to the counsellors to which tickets point. If one had number 5 and enter the

cycle of the counsellor in the first position, one would never reach person

possessing number 5, because cycles are separated, disabling proceeding from

one 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 ticket

number.

Therefore, it

would be the best for a counsellor not to look for his number randomly, but to

start at the standing point with the same number, because this would already

guarantee that he is in the right cycle. The only thing he needs in this case

is moving in the way of permutation cycle, which would (after some steps) lead

him to the counsellor with the same ticket number.

This would be the

best strategy for enhancing the number of successfully met participants in a

‘get acquainted’ game.

PERSONAL

EXPERIMENT

The problem’s

artificiality still worried me and I was not sure if it will truly be possible

to carry the game out in a real life situation. Therefore, I decided to

pre-test the procedure by conducting a similar problem with my classmates.

The example was

simplified by conducting a pre-test on 10 students only. They were all Math SL

students. I chose them because I knew that their level of mathematical knowledge is similar to

mine, so I could understand their reasoning easier and prepare appropriate

explanations.

First of all, 10 boxes were sorted in the

line and written their consecutive numbers on the top of them. Inside, they

were put tickets with numbers from 1 to 10. Then, participants were assigned

numbers from 1 to 10 and presented them their task: they were asked to individually

approach the boxes and try to find their number in the boxes by opening up to 5

boxes each. After that, they were not allowed to communicate with one another. I also explicitly stressed that I want them all to

succeed, so they needed to come up with the strategy that would be the most

optimal 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 situation

The tickets were not allocated randomly, but I always

chose them with thought, so that manipulating variables enabled easier

determination, in which cases the chance of success is the greatest.

Even though participants were told to find the best

strategy, they did not find any and only approached the problem by guessing the

boxes randomly. When they all completed the search, the results showed that

only 6 out of 10 students succeeded.

Then, they were

explained the permutations. And after that, participants were exposed to the second condition. They were once

again challenged to use the best strategy and they approached the problem by

each person starting at the box with the same number as his ticket number. To

find out the trends, they were asked to do this in a few different

examples/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 situation

b)

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 situation

c)

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 situation

d)

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 situation

e)

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 chosen

permutations

Results provided evidence that when students were

informed about permutations, they more easily found their numbers – in two

cases they even all succeeded! As it was aimed to prepare a game in which

everyone would succeed, I was especially interested in the cases in which 100%

of students succeeded. The two cases only shared one feature: they both had

cycles no more than 5 units long. It was also possible to notice that even

though the participants used the best strategy in all cases, the percentage of

successful students declined as the longest cycle in a permutation became

longer.

This occurred because the number of students that

each person could address was limited on 5. If permutation cycle was longer

than that, students with numbers in this cycle could not reach the boxes with

their numbers. Students can for sure win only if their numbers are in

permutations in which the length of the longest cycle do not exceed 5.

If numbers are

assigned randomly to the boxes, there can only be one cycle longer than 5. If

there is for example one permutation with the cycle length of 6, there only

remain 4 numbers that are not used up. Therefore, it is possible to calculate

the chances of all group A counsellors’ success by only calculating the chances

of occurrence of a permutation longer than 5.

THE

PROBABILITY OF OCCURRENCE OF CHAIN LONGER THAN 5

Chains that are

too 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 are

positioned forming a straight line. Tickets can be allocated in this line in

10! 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 specific

ticket number can only be allocated in 10 different ways, because it can be

allotted to 10 differently positioned boxes; two inside numbers can be

allocated in 45 different ways, three inside numbers can be allocated in 360

ways and so on.

If the tickets

would permute linearly, the number of ways in which tickets could permute would

be But because the chains of tickets in our case

are circular, 1 is subtracted. Therefore, the number of ways in which tickets

can be arranged in circles is:

The remaining

tickets can be arranged in different ways, but they are not greater than

5.

The above

reduction of fraction gives a solution of

, with representing all the possibilities, and representing the share of them which are with

the length of l. Therefore, probability that there exists a chain of length l is just .

For the

calculation of possibility of every student’s success, we therefore need to

calculate the chances of occurrence of chains of each different length, from 6

to 10 units.

This is pretty

high percentage, but anyway low enough that it cannot guarantee that all

participants of my ‘get acquainted’ game will be successful. If I wanted them

all to succeed, I would have to make permutations in which the longest cycle

would be no longer than 5. I should not allot numbers randomly, but with

thought, so that no permutation has a cycle longer than 5.

CONCLUSION

I first thought

that simplifying the problem will impede my experiment, but it actually turned

out to be beneficial, because it enabled me to more easily examine how chances

of all participants succeeding could be maximized.

From the analysis

of the conducted experiment, it was possible to conclude that chances of all

counsellors to succeed are maximized by using permutations and permutation

cycles. However, random settlement of the tickets would give only 35.4% of

chances that they all succeed. Therefore, in order for 100% of counsellors to

succeed, tickets should be thoughtfully distributed among group A and group B

counsellors, so that no cycle of the formed permutation is longer than five.

By conducting an

experiment, it was also discovered that performing a mathematical “get

acquainted” game would not be as convenient as it was first believed. Because

“get acquainted” games are thought to be fun, but the involvement of

mathematics could be unpleasant for the ones who are not that confident in

their mathematics, it would be better to conduct it for example as a game on

Math Camps, where there are students who are all interested in mathematics.

Otherwise, the Hundred Prisoners Problem was found out to be difficultly

applied to the real world, however, it would be appropriate as a mathematical

riddle for high school students.

BIBLIOGRAPHY

Flajoret, P. and Sedgewick, R. (2009). Analytic combinatorics online. Cambridge: Cambridge University

Press. Available at: http://algo.inria.fr/flajolet/Publications/book.pdf Accessed 24

September 2017

Weisstein, E. W., (2017). Circular Permutation online. MathWorld. Viewed at 7 November 2017.

Available from: http://mathworld.wolfram.com/CircularPermutation.html

Wikipedia, (2017). 100 prisoners problem. Wikipedia. Viewed 19 September 2017. Available from: https://en.wikipedia.org/wiki/100_prisoners_problem