MATHS a number between 1 and 100,

MATHS EXPLORATION

Application of the
Hundred Prisoners Problem

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

 

 

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