The Josephus Problem

This week’s mathematical installment of intellectual nourishment will be on the Josephus Problem. The Josephus Problem is not a rigorous problem, nor is it hard to solve, but it is a nice easy problem. This is to act as a break from the advanced problems that have been posted recently. Due to the format of the problem, and how it is set up, first the backstory of the problem will be covered, followed with the proving the problem, and finally a nice trick with binary.

The problem arises from a historical story. The scenario is there are Jewish soldiers that have been surrounded by the oncoming Roman army. The Jewish soldiers did not fancy capture, and would prefer death. A plan was devised that the Jewish solider would gather in a circle, and one solider, in what would referred to as position one in the circle would take his sword and kill the solider next to him, and the next living solider would kill the next living solider new to him. This process would continue until only one was remaining, and he was supposed to commit suicide. Josephus however was not a fan of dying, and would much prefer living. So the problem for Josephus is where does he stand in the circle to be the last one standing. In his case there were 41 soldiers in the circle.

To best illustrate the proof, lets start with a smaller circle. To best imagine this, the soldiers are standing in a circle the top of the circle is position one, and then it goes around just like a clock would.  In order to save time I have compiled the winning seat from a couple of circles. So if there is one individual, position one wins, with two people position one wins, with three people, number three wins, with four is one, five is three, six is five, seven is seven. From this small bit of information something can be derived already. The winning seat is always an odd number. This can be seen, because on the first pass through of killing all the even numbers go first. At this point is might seem like the pattern is 1,13,1357,13579,13579... but it is not. According to that pattern if there were thirteen soldiers, position one would win, but that is not the case, in fact position 11 would win. If you do not believe me try it for yourself. So if the pattern is not to go up by two each time, and then cycle back to one, what is? If you notice all the powers of two go to one. That can be easily proven if we know that all the evens go out in the first round. So if there is a power of two number of soldiers, it will get cut in half the first round, and position one will start the second round, and then will half, and half until it cannot be halved again. So the pattern would go 1,13,1357,13579(11)(13), 1...but how does that help us? We know that if there is a power of two number of solider at the beginning of a round then the first position wins. So if the biggest power of two is taken away from a number, the remainer would tell how many position to offset from one to get the winning position. For example, if there where seventeen soldiers that would be the same as sixteen plus one soldiers. So after one kill there is sixteen solider remaining and whoever's turn it is to kill would win the round. So whose turn is it? In the case of seventeen it would position three's turn. Going back to our data set, if there where five soldiers, or four plus one soldiers then three would also win. So if one is the remainder of one from our power of two subtraction, then three wins. So three times the remainder of the power of two, plus one would be the winning seat. Just to be sure lets try it if there were seven soldiers, since we already know the answer, it will allow us to confirm our results. The highest power of two that can be subtracted from seven is four, which would leave us with three. Three times two, plus one equals seven. This matches our results, and confirms it. Going back to the original problem, there were 41 soldiers, 32 is the greatest power of two that can be subtracted from 41 with remainder. 41 minus 31 is nine, nines times two is 18 add now is 19. Josephus should get in position nineteen of the circle.

Something that I will not prove, but might be interesting, if you take the number of soldiers and write in binary, to find the winning seat all you have to do is shift the leading number to the end, and reevaluate the binary.

Sources https://www.youtube.com/watch?v=uCsD3ZGzMgE
              http://www.geeksforgeeks.org/josephus-problem-set-1-a-on-solution/