An uncle of mine asked me this gory problem:
There are one hundred people standing in a circle. They count off beginning at one and ending at one hundred. Since they are in a circle, ONE is next to TWO and ONE HUNDRED. ONE has a sword and kills TWO. He passes the sword to THREE who kills FOUR. And so forth. NINETY-NINE kills ONE HUNDRED and passes the sword to ONE. Then ONE kills THREE and passes the sword to FIVE. This goes on until only one person is left standing. Which number is he?
Let’s try this with a smaller problem and to get a handle on what’s happening. Let’s say that we have 12 numbers. The opening round looks like $$[1,2,3,4,5,6,7,8,9,10,11,12]$$ After the first round of killing, we have $$[1,3,5,7,9,11]$$ with the sword back in 1’s hand. The next round of killing yields $$[1,5,9]$$ and 1 has the sword again. Another round of killing leaves 9 standing (1 kills 5 and passes the sword to 9 who then kills 1). Thus, if we have 12 numbers, then the number that remains is 9.
Let’s now see if we can make heads or tails of what happened. When tackling a new problem, one of the things that I find most useful is to try to collect as much information as possible — all the little (relevant) patterns that we notice. One of the first things we can notice is that we’re basically dividing by 2 at each step and if we keep a count of the numbers remaining after each round we have \([12, 6, 3, 1]\). And so, we can see that the division also appears to be integer division. If we keep track of whether or not we had divisibility by two (1 if we could divide by two and 0 if we couldn’t), then we have \([1,1,0]\) (12 to 6 is divisible by 2, 6 to 3 is divisible by 2, and 3 to 1 is not divisible by 2). Another piece of information that we can collect for ourselves is that \(12 – 3 = 9\).
Let’s try another problem to see what happens. Let’s say that there are 20 numbers. I can tell you immediately that the number standing will be 9, once again. But let’s see this play out.
$$[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]$$
$$[1,3,5,7,9,11,13,15,17,19]$$
$$[1,5,9,13,17]$$
$$[9,17]$$
$$[9]$$
If we look at the number of numbers standing we have \([20,10,5,2,1]\), our divisibility array is \([1,1,0,1]\), and \(20 – 11 = 9\).
What happens if we start with an odd number of numbers? Let’s use \(13\).
$$[1,2,3,4,5,6,7,8,9,10,11,12,13]$$
$$[3,5,7,9,11,13]$$
$$[3,7,11]$$
$$[11]$$
Again we have for the count of numbers \([13,6,3,1]\) which gives a divisibility array of \([0,1,0]\), and that \(13-2=11\).
What happens if we consider a power of 2, say 8?
$$[1,2,3,4,5,6,7,8]$$
$$[1,3,5,7]$$
$$[1,5]$$
$$[1]$$
This gives us our three little factoids of \([8,4,2,1]\), \([1,1,1]\) and \(8-7=1\). Notice anything yet?
Next, let’s try a number of the form \(2^{k}-1\). Let’s go with 15.
$$[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]$$
$$[3,5,7,9,11,13,15]$$
$$[7,11,15]$$
$$[15]$$
And our three factoids are \([15,7,3,1]\), \([0,0,0]\) and \(15 – 0 = 15\).
Do you see what’s happened? Solving this problem is as easy as writing the original number in base 2, finding its 1s complement and subtracting to yield the number that will remain.
Here is how some of the examples from above work out.
For \(n = 13\), we have \(1101\). The 1s complement (found by flipping the bits) is \(0010\), which is the number \(2\) in base 10. Thus, \(13 – 2 = 11\). Notice that \(0010\) is the divisibility array just written in reverse order and omitting the first zero!!
For \(n = 20\), we have \(10100\), whose 1s complement is \(01011\) equating to 11. Thus, \(20 – 11 = 9\), as we had found. Notice that the divisibility array was \([1,1,0,1]\)!!
So, to answer the original question, one hundred in base 2 is \(1100100\), whose 1s complement is \(0011011\) which is 27 in base 10. Thus, the number left standing is 100 – 27 = 73.
But! Notice something in all of these problems. \(100 + 27 = 127 = 2^{7} – 1\), \(12 + 3 = 15 = 2^{4} – 1\), \(20 + 11 = 31 = 2^{5}-1\). This is what a 1s complement of a number does. So, if we want to further simplify this, we have \(100 – 27 = 100 – (127 – 100) = 2\times 100 – 127 = 73\).
Therefore, given any number of numbers arranged in a circle, we can find the remaining position by doubling the number given and subtracting from it one less than the largest power of two less than the double. That sentence is needlessly confusing — that’s why we have mathematical notation.
If \(n\) is our number, then the remaining number is \(2n – (2^{k}-1)\), where \(k\) is the largest integer such that \(2^{k} \leq 2n\).
Try this out with your students. There are lots of little lessons here that will allow discussions about computer science, integer arithmetic in a computer (1s complement vs 2s complement, eg), what division and remainder mean, and so forth. Notice that only an odd number can remain.
In a later post, I’ll look to write up why this works.
If you are looking to perform a magic trick, then try this. Take a deck of 52 cards and note the value of the 41st card if the top card is considered as card #1. Then, alternating, move the top card to the bottom deck or discard it, where the first move is to move the top card to the bottom of the deck. The discards are the cards that were “killed”. When all is said and done, the last card remaining after this process will be the 41st card. Indeed, it should be since \(2\times 52 – 63 = 41\) as per our little experimental discovery.
How many cards do you need to have in order for, say, the 23rd card to be the remaining card? If you had a deck of 52 cards, how could you force the 23rd card to come out on top with our move or discard technique?