Brief History of origin : The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. According to Josephus' account of the siege of Yodfat, he and his 40 soldiers were trapped in a cave, the exit of which was blocked by Romans.
They chose suicide over capture and decided that they would form a
circle and start killing themselves using a step of three. Josephus
states that by luck or possibly by the hand of God, he and another man
remained the last and gave up to the Romans.
With time, the original problem has been adapted and changed to become a generic counting out problem where the number of people and the counting interval varies while the core concept and idea remains same as that of ancient history.
Over that period, mathematicians have worked over this problem to find general solutions to the problem with variables being the number of people standing in the circle and the step chosen for killing.
Without going into unnecessary details(available easily online, may be read by the curious mind), we have been able to achieve a generalization for any n with k = 2 meaning being every second person is killed or counted out.
So for k = 2,
We write the number of people standing in a circle, N as 2^m + p where m is as large as possible. In such a representation, (2p + 1) gives us the original position of the last survivor (The guy standing there can bet on it).While if we require the second last survivor, we write N as 3*2^m + p where again m is as large as possible. In this representation of N, (2p + 1) gives you the original position of second last survivor who may survive if the executioners have mercy on leaving 2 people alive.
So, for a circle of 66 people, we will have :
66 = 2^6 + 2 => 2(2) + 1 = Person on 5th position in the circle at the start survives.
66 = 3*2^4 + 18 => 2(18) + 1 = Person on 37th position survives second last depending upon mercy of the killers.
But what happens if we are confronted with a general situation with a different n,k combination.
For small values of n,k we use something that is called inverse permutation.
Say, n = 20 and k = 3 we solve it as follows :
With inner ring denoting the initial positions while outer ring denoting the elimination order.
XAT 2011 Question
From a group of 545 contenders, a party has to select a leader. Even after holding a series of meetings, the politicians and the general body failed to reach a consensus. It was then proposed that all 545 contenders be given a number from 1 to 545. Then they will be asked to stand on a podium in a circular arrangement, and counting would start from the contender numbered 1. The counting would be done in a clockwise fashion. The rule is that every alternate contender would be asked to step down as the counting continued, with the circle getting smaller and smaller, till only one person remains standing. Therefore the first person to be eliminated would be the contender number 2. Which position should a contender choose if he has to be the leader?
Solution : One liner => 545 = 2^9 + 33. To be the leader, he must stand at 2(33) + 1 = 67th position.
Part 2 of the question I will leave it for you to think over. Leave a comment if you able to solve else I will present the solution in comment for it.
Question : One of the contending politicians, Mr. Chanaya, was quite proficient in calculations and could correctly figure out the exact position. He was the last person remaining in the circle. Sensing foul play the politicians decided to repeat the game. However, this time, instead of removing every alternate person, they agree on removing every 300th person from the circle. All other rules were kept intact. Mr. Chanaya did some quick calculations and found that for a group of 542 people the right position to become a leader would be 437. What is the right position for the whole group of 545 as per the modified rule?
I hope after going through the article you would have been able to develop perspective on these types and problems.
Rate, Like and Share if you like the content on the blog.
You can +1 it when signed in on google, like it when signed in from facebook or tweet about it.
Do help it reach more and more people.
Cheers!
AS
With time, the original problem has been adapted and changed to become a generic counting out problem where the number of people and the counting interval varies while the core concept and idea remains same as that of ancient history.
Over that period, mathematicians have worked over this problem to find general solutions to the problem with variables being the number of people standing in the circle and the step chosen for killing.
Without going into unnecessary details(available easily online, may be read by the curious mind), we have been able to achieve a generalization for any n with k = 2 meaning being every second person is killed or counted out.
So for k = 2,
We write the number of people standing in a circle, N as 2^m + p where m is as large as possible. In such a representation, (2p + 1) gives us the original position of the last survivor (The guy standing there can bet on it).While if we require the second last survivor, we write N as 3*2^m + p where again m is as large as possible. In this representation of N, (2p + 1) gives you the original position of second last survivor who may survive if the executioners have mercy on leaving 2 people alive.
So, for a circle of 66 people, we will have :
66 = 2^6 + 2 => 2(2) + 1 = Person on 5th position in the circle at the start survives.
66 = 3*2^4 + 18 => 2(18) + 1 = Person on 37th position survives second last depending upon mercy of the killers.
But what happens if we are confronted with a general situation with a different n,k combination.
For small values of n,k we use something that is called inverse permutation.
Say, n = 20 and k = 3 we solve it as follows :
With inner ring denoting the initial positions while outer ring denoting the elimination order.
XAT 2011 Question
From a group of 545 contenders, a party has to select a leader. Even after holding a series of meetings, the politicians and the general body failed to reach a consensus. It was then proposed that all 545 contenders be given a number from 1 to 545. Then they will be asked to stand on a podium in a circular arrangement, and counting would start from the contender numbered 1. The counting would be done in a clockwise fashion. The rule is that every alternate contender would be asked to step down as the counting continued, with the circle getting smaller and smaller, till only one person remains standing. Therefore the first person to be eliminated would be the contender number 2. Which position should a contender choose if he has to be the leader?
Solution : One liner => 545 = 2^9 + 33. To be the leader, he must stand at 2(33) + 1 = 67th position.
Part 2 of the question I will leave it for you to think over. Leave a comment if you able to solve else I will present the solution in comment for it.
Question : One of the contending politicians, Mr. Chanaya, was quite proficient in calculations and could correctly figure out the exact position. He was the last person remaining in the circle. Sensing foul play the politicians decided to repeat the game. However, this time, instead of removing every alternate person, they agree on removing every 300th person from the circle. All other rules were kept intact. Mr. Chanaya did some quick calculations and found that for a group of 542 people the right position to become a leader would be 437. What is the right position for the whole group of 545 as per the modified rule?
I hope after going through the article you would have been able to develop perspective on these types and problems.
Rate, Like and Share if you like the content on the blog.
You can +1 it when signed in on google, like it when signed in from facebook or tweet about it.
Do help it reach more and more people.
Cheers!
AS
In a circle of n people from which every kth person is eliminated, let f(n,k) be the last survivor.
ReplyDeletef(n,k) = (f(n-1,k) + k) mod n
That is to say, last survivor is nothing but kth position from elimination sequence of (n - 1) people with k steps.
So, it is given to us that :
f(542,300) = 437
Therefore,
f(543,300) = (437 + 300) mod 543 = 194
f(544,300) = (194 + 300) mod 544 = 494
f(545,300) = (494 + 300) mod 545 = 249
Hence 249th position will be the last survivor position in a circle of 545 people with elimination at every 300th person.
Sir I didn't get the inverse permutation concept
ReplyDeleteYou just write the initial numbering in the inner circle and count your steps on the outer circle and number them from 1 to n as and when they are eliminated. So you keep track of initial position of each person/object eliminated.
Delete