All posts in this series:
- One Potato: A description of the problem
- Two potato: The basic equations
- Three potato: An algebraic formula for the last person left
- Four: A neat calculation method using binary numbers
- Five potato: F# functions to check the various formulae
- Six potato: Using a calculation graph to see the pattern
- Seven potato: Generalizing to other intervals
- More: An efficient algorithm for arbitrary intervals
- Online research: In which I discover that it is called the Josephus problem
Introduction
In my previous blog entry I described a problem from the 2010 South African Mathematics Olympiad. In the next few posts I'm going to show you a few ways of solving the problem. But in this blog entry, I'm just going to set up the equations which the various solutions will all make use of.Let's start with a recap of the problem...
Imagine n people sitting in a circle. Label them 1 to n in a clockwise direction. Imagine walking around the circle tapping every second person on the shoulder (person 2, 4, 6 and so on). People leave the circle when they are tapped. This continues until only one person is left. What is the label of that person?
Derivation
Firstly let's define f(n) to be the label of the last person remaining when there are n people in the circle.
Clearly f(1) = 1.
What we'd like to do is find expressions for f(n) in terms of f(m) where m is smaller than n.
Every second person is being asked to leave with roughly half as many people remaining after each walk around the circle. This suggests that we should consider the cases of n being odd and even separately.
So let's see what happens when there are an even number of people around the circle, say 2n people.
In our first trip around the circle, the n even numbered people will leave the circle. This will leave n odd-numbered people.
Let's re-label these odd people as 1, 2, ..., n. Then the (new) label of the last person remaining would equal f(n). That comes straight from the definition of f(n).
But we are interested in the original label of this last person. That is not f(n) but 2.f(n) - 1. This is because 2k - 1 is the kth odd number.
Hence f(2n) = 2 f(n) - 1.
Next we will find a similar formula for circles with an odd number of people.
We already have a formula for n = 1. All other positive odd numbers can be expressed as 2n+1 for some positive integer n.
Initially the situation looks like this for 2n+1 people:
We would like to express f(2n+1) in terms of f(n). That means still having n people in the circle after the first round of removals.
To do this we need to remove n+1 people. The first n people removed are all even numbered as before. But now the (n+1)th person removed is person number 1. This leaves the following arrangement:
Note that the kth person in the new circle of people has a label of 2k+1.
So we can re-label the remaining people from 1 to n as before, and f(n) is the new label of the last person remaining if we continue the elimination process. But in the original labelling scheme, this becomes 2.f(n) + 1.
So we have shown that f(2n+1) = 2.f(n) + 1.
The basic equations
If we put all of this together, we get the following set of equations (where n is a positive integer):$$ \begin{align*} f(1) &= 1 \tag{1} \\ f(2n) &= 2.f(n) - 1 \tag{2} \\ f(2n+1) &= 2.f(n) + 1 \tag{3} \end{align*} $$
No comments:
Post a Comment