Denote the last survivor in the game which starts with n people
Project: One Potato, Two Potato
120 points
Introduction:
The historian Flavius Josephus was apparently trapped by the Romans in a cave with 40 fellow Jewish rebels. As good soldiers they decided on suicide rather than capture, so they formed a circle and agreed that every third person would be killed until no one was left.
Josephus and a friend were more keen on being captured than their colleagues, so they quickly found the spots to stand to ensure they were the two remaining at the end of the grisly proceedings. Hence, the mathematically inept suffered an untimely demise while Josephus and his friend lived to tell the tale.
This morbid story doesn’t seem like much of a game or a puzzle, but it has the same basic structure as the age old way of choosing someone from a group” the “one potato, two potato” algorithm.
The Game:
In general, when we play the “Josephus game,” there will be a certain number of people standing in a circle, and a “skip number” that tells us how many people to count before removing someone from the circle. In the classical example described above, the number of people is 41 and the skip number is 3.
Example 1: Let’s look at a simpler example. This time, there will be only six people in the circle, but we will keep the skip number at 3. We’ll continue to play until there is only one person remaining. Let’s say people, named Anh, Ba, Chris, Danika, Emma, and Fred, are arranged as shown in Figure 1.
We decide to start counting with Anh. Who is the last person standing?
In this case we started counting with Anh. We count Anh and Ba, and when we get to the third person, Chris, he gets removed from the circle. With Chris gone, we continue counting with Danika. We count Danika and Emma, and when we get to Fred, he is eliminated from the circle. Now there are four people left Anh, Ba, Danika and Emma and he counting continues with Anh. We count Anh and Ba and then Danika is eliminated. The current situation is shown below:
We next count Emma and Anh and remove Ba, and the counting once again continues with Emma. We count Emma and Anh and Emma is removed, so Anh is the person left standing at the end.
Example 2: Now, let’s start with seven people A, B, C, D, E, F and G and removing every fifth person. (we say that the skip number is equal to 5). Who is the last person standing?
Exercise 1. Play the Josephus game with n players with a skip number of k for each of the following values of n and k and determine the last person standing.
a) n = 6, k = 2 b) n = 10, k = 3 c) n = 11, k = 3
Changing the starting Players
What happens if we decide to keep the values of n and k the same but change the person we start the game with? How does this affect the outcome? Let’s go back to the example with seven people and a skip number of five (Example 2 above). Let’s say we have people T, U, V, W, X, Y, Z and start counting with W.
When we started with person A, the last person standing was person F. Who will be the last person standing in the game to the right?
The J(n,k) notation is very useful for describing the last person standing in the Josephus game that starts with n people in the circle and eliminates every kth one. For example, the result in Example 1 can be written as: J(6,3)=1
Exercise 2: Go back to the games that you played in Exercise 1. Find the following:
a) J(6,2) b) J(10,3) c) J(11,3)
Recursion: Using What Came Before
The idea of changing the starting player can be very helpful for finding patters in the Josephus problem. Consider the game with eight people and a skip number of 5, as shown in the figure to the left. After the first step of this game, E is eliminated from the circle and we are left with the figure on the right.
Now what? Well, we continue to play the game as before, or we might notice that we have seen this situation before. This is a game with seven players and a skip number of 5. We already determine that the last person standing in this game is the sixth person around the circle from the starting palyer. In this case, that means that C is the last person standing.
Here is another example of this idea. In Exercise 2c), you determined that J(11,3)=7. That is, in a game with 11 people and a skip number of 3, the seventh person around the circle from the starting person will e the last one standing. How does this step help us determine the value of J(12,3)? Consider the first step of the game with twelve people and a skip number of 3. The first person eliminated is person 3, and person 4 becomes the new starting player. Now there are eleven people remaining, and we know that the last one standing will be the seventh person around the circle starting with person 4. This is person 10.
Finding the Pattern
There is a pattern to how the position of the last survivor changes as we change the number of people initially standing in the circle. To see this pattern, we need to experiment and compute the answer for many different examples. In the table below, the top row represents the number of people in the circle, and the bottom row shows the position of the last person standing when the skip number is 3. The values you have already determined are filled in for you. Fill in the table by either playing the game or by using a “What-came-before” strategy.
Exercise 3:
n 3 4 5 6 7 8 9 10 11 12 13 14
J(n,3) 7 10
What pattern do you notice in the table?
Can you explain this pattern using a “what-came-before” argument?
Make a similar table with a skip number of 4. Can you predict what pattern you will see?
An Easier Variation
A game that’s a little better suited for detailed analysis is the variation where every second person is eliminate – that is, the skip number is 2. The game will officially be played with people named, 1, 2, …, n in a circle (with the numbers going clockwise). We go around the circle clockwise getting rid of every second person (Person 2 is the first to go) until no one is left. For example, if we start with four people, then the people are eliminated in the order 2, 4, 3, 1, so person 1 is the last survivor.
We let J(n) denote the last survivor in the game which starts with n people and has a skip number of 2. (That is, we use J(n) instead of J(n,2).)
Exercise 4: Fill in the rest of the table, either by playing each game or by appealing to the “using-what-came-before” strategy.
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
J(n) 1
n 17 18 19 20 21 22 23 24 25 26 27 28 29 30
J(n)
How is the value of J(n) related to the value of J(n-1)?
What will be the next value of n for which J(n)=1?
How would you describe a formula for J(n) that would allow someone to quickly figure out the last place in line given any n?
Josephus and His Buddy
In the original story, Josephus actually escapes with a friend, so in reality he had to know the positions of the last two survivors of this macabre game. To keep it simple, let’s still use the game with skip number 2, but now we will use F(n) to denote the required position of the friend in the Josephus game starting with n people.
Exercise 5: Play the Josephus game (with every second person eliminated, as above) for various n and record the numbers J(n) and F(n) of the last person alive and of the next-to-the-last person alive, respectively. Find more values than in the table below if you think it is helpful to do so. Remember to try to use things you already know as you tackle larger and larger values of n.
n 12 13 14 15 16 17 18 19 20 21 22 23 24
J(n) `
F(n)
How is the value of F(n) related to the value of F(n-1)?
What will be the next value of n for which F(n)=1?
Is there a direct relationship between J(n) and F(n)?
Further Questions for Explorations
The following problems, as well as the ones above, can be explored with the applet found on the website:
http://webspace.ship.edu/deensley/html5/joseph.html
Exercise 6. Fill in the following table using the “one potato, two potato” game on n people, starting the first “one potato” on person 1. For those not familiar with this method of choosing a person on the playground, this is simply the Josephus problem with every eighth person eliminates. That is, in the table below we use P(n) to mean the same thing as J(n,8) from the previous discussion.
n 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
P(n) `
If the 42 students in this class stand in a circle in alphabetical order and do “one potato, two potato”, who will be the last person left?
Suppose in the game with 6 people, Josephus is person 1 but before the game starts, the Roman leader says, “Hey Joey, you pick the skip number.” What should he say so that he is the last person left?
Is it possible for Josephus to always come up with a response to the previous question no matter how many people are originally in the circle?
Exercise 7: In the Josephus problem with skip number 2, use strong induction to prove that for all integers n≥0, is the game starts with 2^n players, then the person in position 1 will be the last person left.
Exercise 8: In the Josephus problem with skip number 2, if 0≤k<2^n and the game starts with 2^n+k players, use strong induction to prove that the person in position 2k+1 will be the last person left.
Exercise 9: Going back to the original Josephus problem, starting with 41 players with a skip number of 3. Where should Josephus and his friend sit so that they are the last two people left in the circle?
Conclusions:
Now that you explored the Josephus game, I want to know what you learned by doing this project and what strategies and procedures you used to figure out the exercises. Please write a paragraph addressing this.
Collepals.com Plagiarism Free Papers
Are you looking for custom essay writing service or even dissertation writing services? Just request for our write my paper service, and we'll match you with the best essay writer in your subject! With an exceptional team of professional academic experts in a wide range of subjects, we can guarantee you an unrivaled quality of custom-written papers.
Get ZERO PLAGIARISM, HUMAN WRITTEN ESSAYS
Why Hire Collepals.com writers to do your paper?
Quality- We are experienced and have access to ample research materials.
We write plagiarism Free Content
Confidential- We never share or sell your personal information to third parties.
Support-Chat with us today! We are always waiting to answer all your questions.
