Sunday, January 20, 2013

Three potato (an algebraic solution)


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 first post of the series I described a situation where a number of people are sitting in a circle. Every second person is asked to leave. This continues until only one person remains. If the people are labelled 1 to N, what is the formula for that final person?

In the second post in the series I derived the basic equations needed to solve the problem:

$$ \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*} $$
In this post I will use these equations to derive the formula for the label of the last person left.

In future posts I will show a more intuitive way of solving the problem (but still starting from these 3 equations).


Derivation

Equations 2 and 3 allow us to calculate the formula for a number in terms of the formula for a smaller number. Starting from any number we can keep on repeating this process until we get the formula in terms of f(1).

For example, suppose there are 10 people in the circle. Then: $$ \begin{align*} f(10) &= 2.f(5) - 1 & \text{by equation (2)} \\ &= 2.(2.f(2) + 1) - 1 & \text{by equation (3)} \\ &= 2.(2.(2.f(1) - 1) + 1) - 1 & \text{by equation (2)} \\ &= 2.(2.(2.(1) - 1) + 1) - 1 & \text{by equation (1)} \\ &= 2.(2.(1) + 1) - 1 \\ &= 2.(3) - 1 \\ &= 5 \\ \end{align*} $$

We would like to apply this same process to an arbitrary number n. Hopefully a pattern will emerge that will allow us to generate a formula in terms of n.

One potential problem is that we do different things (add or subtract one), depending on whether the number at that step is odd or even. We can avoid this problem if we have a formula which doesn't depend on whether the argument is odd or even.

Fortunately it's quite easy to do. Just note that:

$$ 2b-1 = \left\{ \begin{array}{l l} -1 & \text{if $b = 0$}\\ +1 & \text{if $b = 1$} \end{array} \right. $$
So we can collapse equations 2 and 3 into this equation: $$ \begin{align*} f(2n + b) = 2.f(n) + 2b - 1 & \text{ where b $\in \{0,1\}$}\tag{4} \\ \end{align*} $$

Equations 2 and 3 depend on whether the number we are solving for is odd or even. And the number we are solving for halves after each step. My first instinct on seeing this pattern was to express n as a binary number:

Suppose that: $$ 2^{k} \leq n < 2^{k+1} $$ Then we can express n as: $$ \begin{align*} n = \sum_{{i}={0}}^{k}{a_{i}.2^i} & \text{ where $a_{i} \in \{0,1\}$}\tag{5} \end{align*} $$ Note that the leading binary digit must be 1: $$ a_{k} = 1 \tag{6} $$


We're also going to need a well-known equation for binary sums: $$ \sum_{{i}={0}}^{k-1}2^{i} = 2^{k} - 1 \tag{7} $$ This is really just saying that if all the binary digits in a number are 1, then adding 1 will cause all columns to clock over to give the next higher power of 2. This is similar to how addition works in the decimal system. For example: $$ 10^{3} - 1 = 1000 - 1 = 999 = \sum_{{i}={0}}^{2}{9.10^{i}} = \sum_{{i}={0}}^{2}{(10-1).10^{i}} $$


Let's carry out the steps to derive the formula for f(n): $$ \begin{align*} f(n) &= f( \sum_{{i}={0}}^{k}{a_{i}.2^i} ) & \text{by equation (5)} \\ &= f( 2 \sum_{{i}={1}}^{k}{a_{i}.2^{i-1}} + a_{0} ) \\ &= 2.f( \sum_{{i}={1}}^{k}{a_{i}.2^{i-1}} ) + 2 a_{0} - 1 & \text{by equation (4)} \\ &\text{Let's rewrite this formula as follows:} \\ f(n) &= 2.f( \sum_{{i}={1}}^{k}{a_{i}.2^{i-1}} ) + \sum_{{i}={0}}^{0}[(2 a_{i}-1).2^{i}] & \text{after step 1} \\ &= 2.f( 2 \sum_{{i}={2}}^{k}{a_{i}.2^{i-2}} + a_{1} ) + \sum_{{i}={0}}^{0}[(2 a_{i}-1).2^{i}] \\ &= 2.[2.f( \sum_{{i}={2}}^{k}{a_{i}.2^{i-2}}) + 2 a_{1} - 1] + \sum_{{i}={0}}^{0}[(2 a_{i}-1).2^{i}] & \text{by equation (4)} \\ &= 2^{2}.f( \sum_{{i}={2}}^{k}{a_{i}.2^{i-2}}) + 2^{1}[2 a_{1} - 1] + \sum_{{i}={0}}^{0}[(2 a_{i}-1).2^{i}] \\ &= 2^{2}.f( \sum_{{i}={2}}^{k}{a_{i}.2^{i-2}}) + \sum_{{i}={0}}^{1}[(2 a_{i}-1).2^{i}] & \text{after step 2} \\ &= \text{ ...} \\ &= 2^{j}.f( \sum_{{i}={j}}^{k}{a_{i}.2^{i-j}}) + \sum_{{i}={0}}^{j-1}[(2 a_{i}-1).2^{i}] & \text{after some step j, $1 \leq j \leq k $} \\ &= \text{ ...} \\ &= 2^{k}.f( \sum_{{i}={k}}^{k}{a_{i}.2^{i-k}}) + \sum_{{i}={0}}^{k-1}[(2 a_{i}-1).2^{i}] & \text{after step k} \\ \end{align*} $$
So what I've done is to break the formula on the right into two terms, each with a summation. Then I've progressively eaten away at the left summation while building up the right.

Now we just need to expand and simplify: $$ \begin{align*} f(n) &= 2^{k}.f( \sum_{{i}={k}}^{k}{a_{i}.2^{i-k}}) + \sum_{{i}={0}}^{k-1}[(2 a_{i}-1).2^{i}] \\ &= 2^{k}.f(a_{k}) + 2 [\sum_{{i}={0}}^{k-1}a_{i}.2^{i}] - \sum_{{i}={0}}^{k-1}2^{i} \\ &= 2^{k}.f(a_{k}) + 2 [\sum_{{i}={0}}^{k-1}a_{i}.2^{i} + a_{k}.2^{k} - a_{k}.2^{k} ] - (2^{k} - 1) & \text{ by equation (7)} \\ &= 2^{k}.f(1) + 2 [\sum_{{i}={0}}^{k}a_{i}.2^{i} - 1.2^{k} ] - 2^{k} + 1 & \text{ since $a_{k} = 1$ by equation (6)} \\ &= 2^{k}.1 + 2 [\sum_{{i}={0}}^{k}a_{i}.2^{i} - 2^{k} ] - 2^{k} + 1 & \text{ by equation (1) } \\ &= 2^{k} + 2 [n - 2^{k} ] - 2^{k} + 1 & \text{ by equation (5) } \\ &= 2^{k} + 2n - 2^{k+1} - 2^{k} + 1 \\ &= 2n+1 - 2^{k+1} & \tag{8} \\ \end{align*} $$
Since we can easily calculate k from n, that is our solution.


The calculation method

Let's summarize how we solve this for a particular value of n:
  1. Double n and add 1
  2. Find the largest power of 2 that is less than or equal to n, and double it
  3. Subtract the second number from the first
  4. That is your answer!

Let's check it using our previous example of n = 10: $$ 2^{3} \leq 10 < 2^{4} $$ Hence k = 3.

So: $$ \begin{align*} f(10) &= 2 \times 10 + 1 - 2^{3+1} \\ &= 20 + 1 - 2^{4} \\ &= 21 - 16 \\ &= 5 \\ \end{align*} $$ Which is the answer we got previously!


The algebraic formula

If we want to formalize things we can also express the formula in terms of n only. Simply note that: $$ k = \lfloor log_2 n \rfloor $$ So that: $$ f(n) = 2n + 1 - 2^{{\lfloor log_2 n \rfloor} + 1} \tag{9} $$

Conclusion

So now we have a formula. But it took a lot of algebra. And we still don't have an intuitive feel for why the formula comes out the way it does.

In my next few blog posts I'm going to present a different way of looking at the problem. Instead of going straight for brute force calculation, we are going to apply a bit more insight first.