Hello everybody! Today, I'd like to talk about an interesting problem. It does happen to have a rather gruesome context, but it's a fascinating bit of math. Just like last week, I'm trying out writing articles in more of a problem-solution format in an effort to get all of my members (including you!) thinking creatively as you read, so let me know what you think of the article!
During the Siege of Jerusalem in 70 AD, the story goes, a certain number of Jewish soldiers were captured by the Roman army. They did not want to remain in captivity and instead decided to all die for their cause before the Roman army was fully mobilized to take them in.
They come up with the following scheme to all die. All the soldiers will stand in a circle, and the first person will kill the second in the circle. Then, the next remaining living person (the third) will kill the next person (the fourth), and the next remaining living person after that (the fifth) will kill the next person (the sixth), and so on. The idea is that once the soldiers complete one path around the circle, they'll continue rotating around the circle, always with the living killing the next person in line. At the end, there will be one person remaining, who will (presumably) die at his own hand.
One of the soldiers, Josephus, does not want to die. As he prefers capture to death, he wishes to be the last person remaining in the circle and to make his own decision—to stay alive.
Here's the problem:
If Josephus is with 40 other soldiers (for a total of 41 in the circle), what position should he sit at to survive? By convention, we assume that the positions are numbered 1 to 41 clockwise, the very same direction at which the above process proceeds.
What about the general case? If Josephus is with some number of soldiers (for a total of n in the circle), how can you express the position Josephus should begin at in terms of n (or in relation to n)?
Before you continue reading this article, see if you can begin to answer these questions yourself. What ideas can you come up with?
Here are a couple problem-solving strategies to try:
See if you can begin by trying small cases. Try making a table comparing the number of soldiers to the desired position. What patterns do you see?
This puzzle seems to have something to do with factors of 2. After all, all the even numbered positions are eliminated on the first go-around. Can you harness this fact and expand it?
Don't forget to test it out before you begin reading the hint, solution and discussion below!
HINT: What are the possible numbers of soldiers that give Position 1 as the desired position for Josephus to sit? What property do these numbers share?
Try writing n as a sum of one of the values necessary for Position 1 and a remainder. How can you express the desired position in terms of the remainder? (You do know the desired position is odd—make sure your formula matches that fact!)
If you want to discover something more, try writing both the final position and the number of soldiers in binary.
SOLUTION AND DISCUSSION:
It's time to discuss the problem! This problem, along with the Pirate-Coconut riddle I mentioned in "10 Mathy Things to Try in Quarantine", were actually two of my favorite problems when I started out in the wonderful world of creative math investigations, so I really hope you got something out of trying this one! Even if you just skipped down here to the solution, I hope you can get some value out of the insight behind this problem.
Let's begin! Let's start by working through some cases:
Here's a chart of some of the positions you'll get from working out different numbers of soldiers:
To see a couple of these in action, here are some clips from Numberphile:
Five soldiers:
Six soldiers:
Seven soldiers:
The first thing you should notice here is that all of the positions are odd numbers, a fact that makes sense when you consider that all the even numbers are eliminated on the first trip around the circle as 1 kills 2, leaving 3 to kill 4 and so on. Moreover, these aren't just any odd numbers: they seem to be increasing by 2 each time until, at some point, they reset back to 1.
We'll circle back to the question of why the values increase by 2, but first, let's figure out why they reset at the point they do. Here are the first few values of soldiers where position 1 wins:
Notice that these are the powers of 2! This is the key to understanding the problem: If we are given a number of soldiers that is a power of 2 (let's say 2^k where k is an integer), we will first eliminate all the even numbers, and since the person at the last number, 2^k, is killed (it's even), the person at 1 survives the first round, being given the opportunity to kill the next person in line.
At this point, we will have eliminated half of the soldiers, leaving 2^k/2 = 2^(k-1) soldiers. This is still a power of 2, so the exact same reasoning can be applied, and the person at 1 survives again. (Renumbering the spots 1,3,5,7,9,11... to 1,2,3,4,5,6... makes this even clearer—we're merely eliminating the even numbers again!)
Since a power of 2 remains a power of 2 (and namely, even!) no matter how many times it is divided in 2 (until it reaches the final person), the person at 1 will continue to survive every trip around the circle, and the person at 1 will ultimately be the last man standing.
Think of it this way: the person at 1 is only eliminated if at some point on its turn, the total number of soldiers in the circle is odd, as this would imply the last person would not be killed and would instead kill the person at 1.
At each full trip around the circle (heading back to 1), exactly half of the number of soldiers are left if the number of soldiers is still even.
Therefore, if the initial number of soldiers has a greatest odd factor that is not 1, that will eventually be the number of soldiers, as the number of soldiers continues to be halved each time. This spells doom for the person at 1, so 1 is only the final position when the initial number of soldiers has no greatest odd factor other than 1, or simply, the initial number of soldiers must be a power of 2!
These two arguments together prove both sides of the coin: that the powers of 2 represent the only possible number of soldiers that give a final position of 1 and that all the powers of 2 do indeed give a final position of 1. This is something you often have to prove in math. It's a concept usually referred to as "if and only if": if we want to prove that "the final position is 1 if and only if the original number of soldiers is a power of 2", we have to prove that "the final position is 1 if the original number of soldiers is a power of 2" AND "the original number of soldiers is a power of 2 if the final position is 1."
Sometimes, these two arguments are simply reverses of one another and they seem self-evident, but other times, they require slightly (or very!) different reasoning. Keep this in mind if you're ever proving something for a math competition or just for fun!
So, we now know that all the powers of 2 give a position of 1, and all the non-powers of 2 don't give a position of 1. That's part of the way there, but where do we go from here?
Let's start with a little bit of a manipulation. Let's write n as the sum of two numbers: n = 2^k + m. Here, 2^k is the largest power of 2 that is less than n, and m is simply the difference between the two. We'll be writing a formula for the final position in terms of m.
It initially seems difficult to expand the problem to the non-powers of 2, but it takes a pretty simple little trick.
We merely look at the moment when the circle contains a power of 2 of living soldiers. Then, just like the person at 1 won when the number of soldiers was a power of 2, the person that starts the process at the moment when the circle contains a power of 2 soldiers is the person that wins.
Let's watch the case with 5 soldiers again to see how this works:
It is at this moment (see below) that the circle first contains a power of 2 of soldiers, when the person at 1 has just killed the person at 2 and it's the person at 3's turn, and just as we inferred earlier, the person at 3 wins.
The proof of why the person who starts at this moment wins should be pretty clear to you now. It follows neatly from the proof that the person at 1 wins for a power of 2—we've merely shifted who starts the circle with a power of 2 soldiers, and whoever starts wins for a power of 2.
Let's see how we can take this little observation into a formula—and an explanation as to why the odd numbers increase by 2 each time.
Which person is the one that starts the circle at that moment? It's the person whose turn it is when m people have been eliminated, as n-m = 2^k, a power of 2. We know that the m people will be eliminated at some point on the first trip around the circle as m is less than half of n (if m was more than half of n, then 2^k would not be the largest possible power of 2 that is less than n—see if you can explain why!).
Therefore, we just have to analyze what position's turn it is when m people are eliminated. Notice that the mth person to be eliminated is 2m, so the answer is merely 2m+1.
This completes our formula for the position in terms of m. For n = 2^k + m (with the largest possible integer k, given that m is nonnegative) soldiers, the position of the last man standing is 2m+1.
As m increases by 1 when n increases by 1, this explains why the differences between our positions are 2 (as 2(m+1)+1 - 2m+1 = 2), and it represents a perfect explanation of the sequence we came up with earlier.
For curiosity's sake, note that the odd numbers increase by 2 until they would be too large to continue to increase. For example, if for 16 soldiers, we added 15 + 2 to get 17, we'd get a position that isn't even on the circle. See if you can explain why this makes sense from the explanation we just gave.
Ok, let's apply this to Josephus himself!
Josephus had 40 other soldiers with him, so his value for n was 41. This gives the value for 2^k as 32 and the value for m as 9. Therefore, Josephus must sit in position 2m+1 = 2(9)+1 = 19 to be spared.
Here's something cool:
Have you ever expressed numbers in binary? In binary, you express numbers in terms of powers of 2, rather than powers of 10. Go here for more.
For example, we can write 134 as 1*10^2 + 3*10^1 + 4. It's the product of digits and powers of 10.
In binary (aka base 2), we would only use the digits 0 or 1, and we'd express 134 in a different way:
134 = 1*2^7 + 0*2^6 + 0*2^5 + 0*2^4 + 0*2^3 + 1*2^2 + 1*2^1 + 0 or 10000110.
Here's a neat fact about the Josephus problem. If you express the number of soldiers in binary, then merely moving the first digit to the end gives you the desired position.
For example, if the number of soldiers is 5, the desired position is 3: 5 in binary is 101 and 3 in binary is 011 = 11.
If the number of soldiers is 6, the desired position is 5: 6 in binary is 110 and 5 in binary is 101.
Or, if the number of soldiers is 7, the desired position is also 7: 7 in binary is 111.
In Josephus's case, the number of soldiers is 41 and the desired position is 19: 41 in binary is 101001 and 19 in binary is 010011 = 10011.
This makes sense because you're essentially getting rid of the highest power of 2 if you want to find m, which corresponds to taking off the leading 1. (This gives 01001=1001 for m for n=41.)
Then, we'll find the final position of 2m+1.
Let's start with the 2. Multiplying a binary number by 2 simply adds an ending zero to the number. (This gives 10010 for 2m for n=41.) Then, you just add 1, turning that ending zero to a one. This creates a 1 at the end, and together, it all looks like moving a 1 from the end to the beginning. (This gives 10011 for 2m+1 for n=41.)
See if you can fully convince yourself why this is true.
VARIANTS:
The best thing about a good open-ended math problem is you can expand it any way you'd like. The Josephus Problem doesn't end here. There are a lot of variants on how the process is executed, and there are a lot of questions you can ask about the setup.
First, what if we skip a person? In the original setup, we assumed the first person killed the very next person, the second person, in line, and so on, with each person killing the very next person. What if the first person skipped over the second person, killing the third instead, and every other person followed suit, skipping over one person? What if everyone in the circle skipped over two people? What if they skipped over three?
See if you can figure out what patterns (and even what formulas) these setups create.
If you want to play with it with a simulation as opposed to trying things out by hand, there's some great software here on GeoGebra. On the software, k corresponds the "count" for each step, i.e. every kth person is killed each time. For the problem we've investigated for this article, k equals 2 because every second person is killed each time (the odds, as the killers, are spared). If we skip one person, k equals 3, and if we skip two, k equals 4.
See what you can come up with, and leave it in the comments below!
There are some other variants to this problem, but I encourage you to look for and try them yourself, and tell me what you come up with.
ANOTHER CHALLENGE:
If you've ever played the game Ninja, you can think about the Josephus problem in terms of the game if you only needed one hit to get out, the game only proceeded in one direction, let's say clockwise, and the players were "perfect", always striking each other out successfully. Your goal is to start in the position where you will win the game. What other restatements of this problem can you write? Leave them in the comments and I'll let you know what I think!
PROGRAMMING: This is a really popular problem in the world of coding, so if you're into that kind of thing, I'd love to see what you come up with from this angle as well.
I believe this video should help you out: https://www.youtube.com/watch?v=fZ3p2Iw-O2I
RESOURCES:
My number one source (and all picture credit) goes to this amazing Numberphile video:
If you want to learn a little bit about the real Flavius Josephus, check out this video:
And here are two great articles on the problem:
https://medium.com/@rrfd/explaining-the-josephus-algorithm-11d0c02e7212 (this one is also more coding-based!)
CONCLUSION:
Thanks for checking out this week's article! I apologize for the slight delay—I spent all weekend participating in the amazing inteGIRLS Puzzle Contest 2020, an incredibly well-run puzzle competition that hosted 1500+ girls online across the world! It was a great experience, and I'd highly recommend checking out inteGIRLS's site here. The inteGIRLS team are also teens, just like me and most of you, and I'm so inspired by the work they've put into their nonprofit, so shout out to them for their phenomenal work!
I hope you enjoyed this week's article, and feel free to leave any questions or comments in the comment section or hop on over to the forum to discuss even more! Have a great week everybody!
Komentarze