One potato (the problem statement)

---

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

Some months back I discovered the web site of the SA Math Foundation including past papers for the South African Mathematics Olympiad. Back in high school I used to love solving Mathematics problems. So I downloaded a bunch of question papers and starting solving some of them.

This series of blog postings describes some interesting solutions I found to one of the problems.

[Edit: I've since discovered that it is known as the Josephus problem]

---

The problem statement

One of the first papers I glanced at was the 2010 senior paper, second round.

The first question described a situation in which there are 10 people in a circle, and every 2nd person is asked to leave the circle. This continues until only one person remains. If we number the people 1 to 10, and eliminate person 2 then 4 and so on, what is the number of the last person left?

So it works much like the children's game "One potato, two potato", except that every 2nd person is eliminated, not every 8th person.

---

The plan

Later I was thinking back to the problem and made a fortuitous mistake. I accidentally thought that the problem was phrased as 2010 people, not 10 people (Math Olympiad problems often use the current year in the problem statement).

So I ended up solving the problem generally, not just for the number 10 (which can easily be solved by brute force).

In the next few blog postings I intend to show you a few solutions to the problem. As I did with the Pyramid of Hexagons problem, I want to provide an algebraic proof as well as intuitive insight into why the proof is true.

So my plan is as follows:

• First I will generate the basic equations which all the solutions will use
• Thereafter I will provide my first algebraic solution
• Then I will try to give some insight into an interesting pattern behind the formula Hint: There is a link to the binary number system.
• Then I will give a simpler proof inspired by this pattern.
• And finally I will provide the code I wrote to generate the illustrations.

---

Disclaimer

While the visualization should be very helpful, it's not going to be as striking as my Pyramid of Hexagons visualization.

So I'm hoping that a reader of this blog will be able to find an even more elegant way of explaining the formula.

---