The Josephus Problem:

Rama Salami
Rama_Salami@hotmail.com
Math 213 -- Mathematics with Mathematica, Fall 2009 
December 10, 2009

Abstract:

My project investigates Josephus problem ,how it works and who will be the last survival between the group,and also it looks for the pattern between (n) number of people and the last survivor person.  I also looked for an equation that we could use in order to get the last survival before playing the game(theoratical part),and then one can make sure of his answer using mathematica (actual part),and then i discussed the way it works.

Section 1. Introduction

1.1 Background

Flavius Josephus was a Jewish Historian in the first century .He wrote about a group of Jews in a cave ,who.rather than surrender to the romans,chose to die by thier hands,and since suicide was forbidden for religious reasons,they decide to put each other to death,one-at a time,so the last one remaining would have to commite suicide or suffer at the hand of the romans.
that was the whole purpose for Josephuse problem ,to guess before starting who would be the last survival,and that was the whole purpose of my project,but instead i am doing it as a game.

1.2 Problem Statement

a. Who would be the last survival between the group ,if we killed every other person?  
b. what would be the relationship between the last survival and (n) number of people in the group?

1.3 Useful Commands

a. One of the commands that was necessary for my project is Table,which list the circles(which represent the people in the group) in different position.

Table[Circle[{Cos[i], Sin[i]}, 0.1], {i, 0, 2 Pi, Pi/4}];

b. Also one of the most important command is InversePermutation[Josphuse] command which gives the last survival between the group ( this command should comes after a Needs["Combinatorica`"]).

?InversePermutation

InversePermutation[Josephus[10,2]];

c. Also , the Inset command which allow me to insert numbers in a specific position on my graph.

?Inset

Graphics[{Red,Inset[i,{Cos[(i*2Pi)/d],Sin[(i*2Pi)/(d)]}]}];

?Graphics

1.4 File Structure

In section 2 , i will explain my project step by step, and show how did i approch my final graph, and also i will show how the commands that i used , and how it worked out
And in section 3 i will mention the pattern that i got in order to guess the expected survival before the actual play of the game,  and also i will mention the future work for this project and what could be to improve this project.

Section 2. Main Work

2.1 Creating a circle of circles:

First, in order for me to get a cirlcle of circles, i decided to create a table of circles , and then i specified the correct position for each one using (Sin (i) and Cos (i)).

Graphics[Table[Circle[{Cos[i], Sin[i]}, 0.1], {i, 0, 2 Pi, Pi/4}], Frame -> True]

2.2 Manipulating number of circles:

Now,i am trying to manipulate number of cirlces ,so that will be my variable.

Manipulate[Graphics[Table[Circle[{Cos[i],Sin[i]},0.1],{i,0,2Pi,2Pi/d}],Frame->True],{d,3,30,1}]

Needs["Combinatorica`"](*i had to use this command in order for me to be able to use InversePermutation for Jusephus command*)

Then i used the Josephuse command to check which circle will stay till the end.

InversePermutation[Josephus[10,2]]

Here i found that for 10 people the last survival will be person # 5.

2.3 Coloring the circles:

Now I can color the dead circle using If statement,So,if the cirlce is dead ,it will appear as black desk,if it is still survive ,it will stay as white circle.

Manipulate[Show[Table[If[MemberQ[Take[InversePermutation[Josephus[d,2]],d-1],(i*d)/(2Pi)],Graphics[{Black,Disk[{Cos[i],Sin[i]},0.1]}],Graphics[Circle[{Cos[i],Sin[i]},0.1]]],{i,2Pi/d,2Pi,2Pi/d}],Frame->True],{d,3,30,1}]

2.4  Numbering the circles:

Then , I numbered the circles, So that i could know which person stays tilll the end ,and he will be the last survivor.

Manipulate[Show[{Table[Graphics[{Red,Inset[i,{Cos[(i*2Pi)/d],Sin[(i*2Pi)/(d)]}]}],{i,1,d}],Table[If[MemberQ[Take[InversePermutation[Josephus[d,2]],d-1],(i*d)/(2Pi)],Graphics[{Black,Disk[{Cos[i],Sin[i]},0.1]}],Graphics[Circle[{Cos[i],Sin[i]},0.1]]],{i,2Pi/d,2Pi,2Pi/d}]},Frame->True],{d,3,30,1}]

Section 3. Conclusion and Future Work

3.1 Summary:

It appears that there is a pattern for the survivor,and that pattern is: when the circle size n is a power of 2 , the survivor is always person number 1(i.e when n =8=2^3  or 4=2^2 or 16= 2^4 .......etc the survivor will be person number 1),But, for n between the powers of 2 each time n increases by 2 (skipping one and get to the next one).
After i got this pattern i figure out also that when the number start to increase by 2 each time killing it stopes when it hits the power of two.  So the series of survivals that we will get when we increase n( number of circles) by one is as follows:
n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
f(n)	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1
And i found out also that when we hit the power of two we came back to number (1),which is basically still skipping one cirlce and get to the next one which is number (1) at that circle with n number of people.

3.2 Discussion:

Here, i want to discuss how to solve the problem when every other person will be killed.  so if we let f(n) donate the position of the last survivor when we have (n) initially the number of people in the circle. For the first time around the circle ,all the even number will die, for he second round,the new even numbers will die and so on, so,if the inital number of people was even ,then the person in position x during the second time around the  circle was orginally in position 2x-1 .  So,the person in position f(n) was orginally in position 2f(n)-1, that gives us the equation f(2n)=2f(n)-1.
In the other hand,if the inital number of people was odd so we know that person 1 is dying f rthe first time around the circle,for the second time around the circle then a new 2nd one will be killed ,then a new 4th one ......etc,in this case the person in position x was originally in position 2x+1.  This gives us the equation: f(2n+1)=2f(n)+1. 
Using mathematica it was quiet easy to figure out what is the pattern in josphus problem,and also it was easy to follow and prove.  After i have done this project my knowledge in mathematice has been extended ,now i know that we could also include games to be done using mathematica not just to prove and graph things.  that was a good experiance in mathematica.

3.3 Future Work

After i did this part of the project, i was trying to make it a real game.  My strategy was that i want to choose one person from the group and check if he is the survivor or not, and one can make this guess using the pattern that i have mentioned before, if his guess was right it would show you won, if not it would show you lose.
But the problem is that i couldn' t make a relation between the picking and the actual game, and that might be the future work for this project.

Section 4. References

1. My lab instructure (Prof.Chris.Hanusa).
2. The text book that we are using for Math 213 W( Discovering mathematics with mathematica by Robert Cowen and John W.Kennedy).
3. Wolfram.com.
4. http://en.wikipedia.org/wiki/Josephus_problem