Introduction:
In first century AD, there was a historian aka scientist was living in jewish town called Yodfat, his name is Flavish Josephus. On his time, there was constant war happening between Romans and Jews. At once, Romans sieged the town Yodfat and it remained sieged for many days. And people had demand for food and essential commodities and they had no other choice but either surrender or embrace death. There were 40 solders with him in a cave for so long that they wanted to commit suicide. Everyone agreed but Josephus had different plan in his mind. He knew if he propose the idea of surrendering to Romans, then rest of the 40 soldiers will turn against him. so he devised a plan to escape.
He proposed an idea that everyone has to stand in circle and they have to kill the person stand next to him in circle until the last person stand. finally, the last person has to commit suicide. His plan is to stand in the place where if he stand he would be the last person, so that, once everyone is dead, he can surrender to Roman soldiers so that he may live.
Preface:
Mathematics is all about life application. Many believe that if you practice mathematics, either you can be a lecturer or an accountant. But it is not true. In this series we are going to see all the life application. Take the above problem as example. Josephus had a calculation in his mind that in which place if he stand he would survive. Will you be able to do it? I know you have taken your paper and pen to calculate for 41 people. But it is not the point here. When you derive a function it should not be limited to a single number. It should be common or applicable to any given number.
Mathematical Thinking:
For starters, if you are not sure how to derive a function, it is always a best practice collect data points, more number of data points the accurate the prediction will be. This is not my original article, I learned it from a mathematician called Daniel Erman from University of Wisconsin (through Numberphile). Let us see it from the following example, number of people can be represented as "n", and winning position can be defined as w(n).
Lets take example, If n=7, then the winning position will be w(n)=7, though the killing looks like a sequence in the beginning, very soon it will become chaos. So keeping that in mind, find the following table to reference.
| n | w(n) |
| 1 | 1 |
| 2 | 1 |
| 3 | 3 |
| 4 | 1 |
| 5 | 3 |
| 6 | 5 |
| 7 | 7 |
| 8 | 1 |
| 9 | 3 |
| 10 | 5 |
| 11 | 7 |
| 12 | 9 |
| 13 | 11 |
| 14 | 13 |
| 15 | 15 |
| 16 | 1 |
| 17 | 3 |
| 18 | 5 |
| 19 | 7 |
Are you noticing the pattern? I am sure you can, Here is my understanding
- Winner cannot be a person who stand in even seat. (Of course it makes sense that all the even people will surely get killed in the first round of execution), it is purely a fight of an odd number seats.
- W(n) always increment by 2 until n>w(n). if the increment w(n)>n, then it resets to 1.
- The reset happens only when the number is 2^x. Ex, 2,4,8,16,32.. It makes sense because if n is 2^x (x is a real whole number), when the first round is over, still the kill has to start from 1st person and remaining number of people are 2^x. it will continue till the last person.
Now we can start draw our conclusions.
Solution:
if we can bring the headcount to 2^x, then we will know whoever standing next will be the winner. because after that game is fairly straight forward. How we can do this. we can split the function as follows.
n = 2^x + r where n defines the total number of people, x defines maximum possible power of 2 in the given number and r defines the remaining people in the whole n. in this case if we eliminate r number of people, then remaining people will be 2^x, then we know as per our previous learning who ever starts will be the winner.
Lets see an example,
Given Number of people are 27,
Then Maximum possible 2^x = 16 where x=4, then representation can be 27 = 2^4+ r where r=11, now the eleventh person kill will be 22nd person. then the winner will be 23rd person.
We will check with out known number from the table.
n=11, then possible maximum 2^x = 2^3 then r value is 3, then the formula can be
w(n) = (2r)+1, that is (2*3)+1 = 7 (Verify it in the table)
Now let us come to Josephus problem, there were totally 41 people including him, then let's apply the formula.
n = 2^x+r --> n = 41, then 41=2^5+9. Now apply formula w(n)=2r+1; w(41)=(2*9)+1 = 19
Josephus must have stood in 19th position. His knowledge in mathematics saved his life, But we have no clear evidence to prove whether this story is true or not. but the point her is "Math is life saver" If you are good at mathematics, surely your life will be saved in trouble some situation.
Whether you are good at math or not, it doesn't matter. How you approach a problem will give better clue for the solution. In the upcoming episodes we will see more interesting math and real life application.
Alternate Solution:
Before we wind up this article, i have an another simple trick to creak this same problem, it needs little knowledge on binary numbers and how it is represented.
Let's take the same 3 examples to find out the easy solution.
Ex1: n= 27, Write down this number in binary =11011, Now move the MSB to LSB, that will be the solution of out problem statement. that is, 10111 in decimal 23,
Ex2: n = 11, binary = 1011, MSB move to LSB 0111, in decimal 7,
Ex3: n= 41, binary= 101001, MSB to LSB that is 010011, in decimal 19.
Conclusion
This is the beauty of mathematics, it not not necessary problem in only one way/method. It is possible to solve in multiple ways. Stay curious, Question everything.
If you like this article and like to watch this explanation in video, it is available in 2 languages (Tamil and English). You can check out the links here.
We are available in YouTube and Facebook, if you like what we do, feel free to subscribe, share with your friends.
Reference Links:
Courtesy:
Numberphile
All the Clipart Pages
0 Comments