The Josephus problem - Jack the Ripper strikes again !!
Recently when I appeared for one of the management entrance exams, I found two very interesting questions in the logical reasoning section. I could only answer one of them, and that too took a long time, so couldn't dare to attempt the second one as well, for the fear of losing valuable time.
Later on I found out that it was a variant of the popular "Josephus Problem" and boy, had I read the wiki page earlier, I would have solved the two questions in less than a minute !!
Here's a variant of the question :-
Assume that there is a circle of 997 people. And Jack the Ripper is free and on a killing spree. But he has strange rules. He says that he will kill every alternate person in the circle and leave the next one alive till he traverses the circle once. After that, he would again get the alive persons to form a smaller circle and the hacking (of necks 😀 would begin again and so on till he has been left with only one person.
The question is, for 997 people, what would be the position to stand in, if you want to be the lone survivor.
Another variant is for "n" people, and for a separation distance of "x" (in our case, n=997 , x=1) what can be the generalized position in terms of n and x ?
Later on I found out that it was a variant of the popular "Josephus Problem" and boy, had I read the wiki page earlier, I would have solved the two questions in less than a minute !!
Here's a variant of the question :-
Assume that there is a circle of 997 people. And Jack the Ripper is free and on a killing spree. But he has strange rules. He says that he will kill every alternate person in the circle and leave the next one alive till he traverses the circle once. After that, he would again get the alive persons to form a smaller circle and the hacking (of necks 😀 would begin again and so on till he has been left with only one person.
The question is, for 997 people, what would be the position to stand in, if you want to be the lone survivor.
Another variant is for "n" people, and for a separation distance of "x" (in our case, n=997 , x=1) what can be the generalized position in terms of n and x ?
Replies
-
suyashTo clarify,
After Jack traverses the circle once, the people left will be 1, 3, 5, 7, .... till 997
After Jack traverses the circle second time, the people left will be 3, 7, 11, 15, .... till 995
and so on...
(this is for n=997 and x=1) -
cooltwinsi think the answer is 971st position from the start.
-
Ankita Katdare@suyash: Are you sure that the clarification you wrote is correct?
In first circle it is: 1, 3, 5, 7, .... till 997
But in 2nd circle it will be: 1, 5, 9, 13 till 997
Correct me if I am wrong. -
Saandeep SreerambatlaI guess in this case AKD the person in position 1 will never die?
-
Ankita Katdare
@CT: Could you put a mathematical solution?cooltwinsi think the answer is 971st position from the start. -
cooltwinscalculation:
for Josephus Kind of problems the solution is: if n(no. of people)=2^x+y so that 0
so for n=997 => y=485 => safest place is 2*485+1=971 -
Ankita Katdare
@ES: Yeah. That's why I asked.English-ScaredI guess in this case AKD the person in position 1 will never die?
@CT: I had got that 2^9 = 512.
997-512 = 485.
I was confused about how to proceed.
Is that a standard formula you used?
And Well, what are the other 'Josephus Kind of problems'? -
cooltwinsyeah you were right till that step.
that is not standard for any Josephus problem it is the solution only for alternate counting kind.
there are other kinds in the sense it is not necessary that alternate people only must be killed. if the problem goes as every 10th person is killed or every 5th person is attacked that solution will vary.
but since suyash had given problem of the first kind the solution can be used. -
Ankita Katdare@cooltwins: You should write a program in C/C++ to solve the Josephus problem for 'n' people.
@all newbies: This could be your mini project. 😉 -
suyash
Hi AbraKaDabra,AbraKaDabra@suyash: Are you sure that the clarification you wrote is correct?
In first circle it is: 1, 3, 5, 7, .... till 997
But in 2nd circle it will be: 1, 5, 9, 13 till 997
Correct me if I am wrong.
When I gave the clarification, I forgot to mention why during the 2nd traversal 3 will get killed and not 1.
The reason for this is that, the circle gets "progressively" smaller as you continue to kill people one by one. So in the end when 997 survives, we don't start over from 1 again and kill 3, but kill 1 directly because 997 (the person before him survived)
that's why in the 2nd traversal, the people alive are :-
3, 7, 11, 15, ....
I hope I solved your doubt... -
ISHAN TOPRE@CT:cool twins you said n=2raise to x+y
i.e;n=2^x+y
now if n=997 and x=1
so we will have 997=2^1+y
hence y=997;
so from where did you get safest position=2Y+1?
@AKD:How you got 2^9=512?
can you please explain the steps you followed???
You are reading an archived discussion.
Related Posts
Wipro working in th field of Super Computer for past three year and developing the fastest IndianSuper Computer for ISRO and will become the India's fastest Super Computer for the...
can someone please elaborate about marshalling box in a transformer?
it is having RTD(or thermocouples) for measurement of oil and winding temperatue only or something else also?
1. Building a Multiple-Criteria Negotiation Support System
2. An Exploratory Study of Database Integration Processes
3. COFI approach for Mining Frequent Item sets
4. Online Random Shuffling of Large Database...
1. Fabrication of Remote operated weapon System
2. Automatic double axis Pneumatic JCB
3. Automatic Car Parking System for apartment Building
4. PLC based automatic Multi-machine Lubrication System
5. Electronic...
Samsung has developed faster computer memory module i.e DDR4 RAM and is capable to rad and write twice time faster then the previous one (DDR3).The transfer rate of DDR3 is...