Welcome to NRICH.

 
The Josephus Problem
By Jonathan Fernando on November 18, 1998:

Currently I am working on a mathematical puzzle called the Josephus Problem. It is a fascinating problem involving the elimination of a selected group by arranging them in a circle in such a way, that by consistently counting the same digit around the circle and removing those that you land on, the unwanted that you have strategically positioned will hence be discarded. My aim is to possibly derive a general solution/model. If you know of any books that could aid me with my limited mathematical knowledge I would be extremely grateful for the suggestions.

By Alex Barnard on November 26, 1998:


A partial solution
From: Alex Barnard
On: 11/26/1998 at 14:53

Hello there...

If I understand the problem correctly I've seen something like it before. Here is a solution for a special case of the problem.

A certain number of people (lets call it n) sit round in a circle and they are numbered 0,1,2,3,...,n-1. A person with a paint gun walks round starting at 0 and he does the following: Ignoring people with paint on them; skip one person and paint the next.

So suppose we have 10 people (0,1,2,3,4,5,6,7,8,9). Then our person will paint people 1,3,5,7,9. This leaves 0,2,4,6,8. He will now skip person 0 and paint 2; skip 4 and paint 6; skip 8 and paint 0; skip 4 and paint 8. This means that 4 is the person who survives.

So how do we work out who survives? Let me use the following notation: If we start with n people and person k survives I shall write s(n)=k [ie. the survivor from n people is person k].

If we only have one person then he survives, so s(1)=0.

Suppose we have an even number of people (say 2n). They are called 0,1,2,...,2n-1. On the first circuit we paint people numbered 1,3,5,...,2n-1. Now notice that we are back to a very similar situation to before. Now we have n people called 0,2,4,...,2n-2. Now suppose that we know that s(n)=k. How can we use this to help with our current situation? Well we know that the k'th person survives, but in our situation, the k'th person is actually called 2k. So s(2n)=2s(n).

So we have seen that doubling the number of people simply doubles the
number of the person who survives.

Now suppose we have an odd number of people (say 2n+1). They are called 0,1,2,...,2n. On the first circuit we paint people numbered 1,3,5,...,2n-1 and 0. We now have n people left called 2,4,6,...,2n. Hopefully you can now see that s(2n+1)=2s(n)+2.

So we have the following 3 relations:

1) s(1)=0
2) s(2n)=2s(n)
3) s(2n+1)=2s(n)+2

From these we can work out any solution we want. For instance, who survives from 100 people?

Well s(100) = 2s(50) = 4s(25)
s(25) = 2s(12)+2
s(12) = 2s(6) = 4s(3)
s(3) = 2s(1) + 2
s(1) = 0

So s(3) = 2
s(12) = 8
s(25) = 18
s(100) = 72

So now you can do any specific number. But is there a quick way of doing it on sight? Well I'll just give you the solution and let you think about why it is true! Hint: it is to do with equations 1,2 and 3.

Write the number n in binary, remove the left most 1 and add a 0 on the end. This is the binary number for the survivor.

----------

This all suggests that for the more general problem the answer will probably be something to do with a different base than 2 but I haven't had time to think about it yet.

AlexB.

By Alex Barnard on November 28, 1998:


A solution
From: Alex Barnard
At: Anonymous
On: 11/28/1998 at 16:23

Okay... I thought about the problem last night and came up with the following.

We are now sitting n people in a circle and removing every m'th person. As before we will number the people 0,1,2,3,...,n-1. As before I shall write s(n)=k to mean that person k survives when we start with n people. However, slightly different to before, I will allow k to be larger than n. In this case if I say person numbered 100 survives from 90 people then what I actually mean is that the person numbered 10 survives.

Suppose we start with mn people in a circle (so they are numbered 0,1,2,...,mn-1). We will remove people numbered m-1,2m-1,3m-1,...,mn-1 and then m. We are now left with (m-1)n-1 people in a circle and we are starting from person number m+1.

Unlike in the case m=2 the people are not numbered so nicely this time. If you actually try this out you will see that we have people numbered with jumps every so often. So we want some function (f say) which goes from people numbered normally to people numbered with jumps. Now I'll just tell you what it is; if you really can't work out why then I'll go into more detail in another reply:

f(x) = x + [x/(m-1)]

where [y] means the integer part of (ie. we throw away anything after the decimal point).

So, using this function you will now find that:

s(mn) = f( s((m-1)n-1) + m ) [Try it and see!]

If we now start with mn+1 people (numbered 0,...,mn) we will remove people numbered m-1,...,nm-1 and then m-2. So we now have (m-1)n people and we are starting on person numbered m and they have a strange numbering like before. Looking carefully we find that:

s(mn+1) = f( s((m-1)n) + (m-1) )

Similarly, we get a whole series of equations:

s(1) = 0
s(mn) = f( s((m-1)n - 1) + m )
s(mn+1) = f( s((m-1)n + 0) + (m-1) )
s(mn+2) = f( s((m-1)n + 1) + (m-2) )
...
s(mn+(m-1)) = f( s((s-1)n + (m-2)) + 1 )

And now using all of these we can work out who survives.

I haven't yet seen whether anything nice can be done with these equations to give a solution to the problem which can just be read off of the base m expansion. If I have more time I shall look for one.

Please ask any questions that you have about this problem.

AlexB.

By Alex Barnard on December 2, 1998:

Some more results

Here is something really quite obvious that I appear to have missed until now...

Using the same notation as before (n people, skip by m, s(n) is the survivor number) then if you have understood the way I did the calculations from the previous messages hopefully you should see that:

s(n+1) = s(n) + m

Again, if this goes over the highest numbered person (n) then we should subtract n+1.

In more mathematical notation:

s(n+1) = s(n) + m (mod n+1)

[Note: This turns out to be similar to an answer that I was sent by the original setter of the problem]

There are certain properties that this has:

Most of the time we can ignore the mod n+1 bit because the answer is not too large. So there are long strings of numbers which are basically the m times table.

When we do have to use the mod n+1 bit the answer is small (because we didn't have to use the mod bit before --- think about this!!).

Because n increases the runs between the above resets get longer and longer.

Hope someone finds this useful...

AlexB.

By Alex Barnard on December 10, 1998:

Even more

Last time we saw that s(n+1)=s(n)+m (mod n+1) gives the last person to be got... What if we don't want to know the last person but the second last person...

Well, exactly the same reasoning will give the same equation as above. The only thing that will be different is the initial condition. Before this was s(1)=0. Now we have to choose s(2)=m-1 (mod 2) as the initial condition. Similarly we can get results for the third last, etc. to die.

Can we combine these in any way?

Let us define s(k;n) to be the number of the k'th person to be got if we start with n people (numbered 0,1,...,n-1).

As before we know that s(1;n)=m-1 (mod n) because this is exactly how we pick the first person.

After we have removed one person we have people numbered starting at m (mod n), we have one less person than before and if we wanted to know about the k'th person before we will now want to know about the (k-1)'st person.

So, s(k;n) = m + s(k-1;n-1) (mod n).

Using this we can that we could define s(0;n) as -1.

Right, how do we use the above formula to get some answers. Well, we use a table... Down the left column we write the current value of n (0,1,2,3,4,5,... etc. until you run out of paper) then we write a column of -1's (these correspond to s(0;n). To work out the next column we add m to the number that is one left and one up (and then we reduce it modulo n). And so on...

For example (for m=2):

0 -1
1 -1 0
2 -1 1 0
3 -1 1 0 2
4 -1 1 3 2 0
5 -1 1 3 0 4 2
6 -1 1 3 5 2 0 4
7 -1 1 3 5 0 4 2 ...
8 -1 1 3 5 7 2 6 ...
9 -1 1 3 5 7 0 4 ...
10 -1 1 3 5 7 9 2 ...
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .


So what we see along the top diagonal is the number of the last person to be got (0,0,2,0,2,4,...). The diagonal before is the second last to be got (1,0,2,3,0,2,...). And so on...

Hopefully you can already see lots of patterns than can be explained.

AlexB.

By The Editor:

There is a good discussion of the Josephus problem in "Concrete Mathematics" by Graham, Knuth and Patashnik.