A friend of mine gave me this puzzle.
N (could be 25, 10, 100 or 2: any positive integer) number of people stand in a circle. They are numbered from 1 to N. Each is armed with a dagger. Shown below is an example with N=9.
All of them perform an activity which is this:
The first in the circle (whom we identify as number 1) kills the second one. Then the next (3rd) kills the 4th one. The next (5th) kills the 6th and so on. This continues until only one person is alive.
Essentially every person kills the next person alive. Then the next person alive kills the person next to him that is alive. Only one person is killed at a time.
If there are 100 people in the circle initially (1,2,3,...100) which of them remains alive at the end?
Abstracting it, if there are N people, which person is the winner?
Solution:
If there are 2^n people (meaning 1, 2, 4, 8 etc), if we work out the solution, we will always find the winner to be the person number 1. Let's assume there were 8 people in the circle.
After the 1st "round", persons 2,4,6,8 would have been killed leaving 1,3,5,7 standing with the dagger in the hands of the 1st person. In the 2nd round, 1 will kill 3 and 5 will kill 7 and dagger is back in the hands of the 1st guy with number 5 as the only other person still standing. In the 3rd round, 1 will kill 5. Thus 1 will become the winner.
Now if the number of people is 100 initially, we let the activity or game proceed until the number of players alive reaches 2 to the power of some integer. Here we will wait until 100 reaches 64. Once it reaches 64, we know that the person whose turn it is to kill will win.
Now, the question is: whose turn is it when the number of people alive is 64.
Since 100 became 64, 36 people have died. These are numbers 2,4,6,8 etc till 72. And it's the turn of the 73rd person now. The number of people alive are all those from 73 to 100 (total 28) and those from 1,3,5,7 till 71 (total 36). 28+36=64.
Person number 73 will be the winner.
Interestingly if there are 2^n - 1 people in the circle, the last one will be the winner. If you are the 1st one, make sure there are 2^n people in the circle. If you are the last, make sure there are 2^n - 1 people. n is some positive integer.
If there are 100 people in the circle initially (1,2,3,...100) which of them remains alive at the end?
Abstracting it, if there are N people, which person is the winner?
Solution:
If there are 2^n people (meaning 1, 2, 4, 8 etc), if we work out the solution, we will always find the winner to be the person number 1. Let's assume there were 8 people in the circle.
After the 1st "round", persons 2,4,6,8 would have been killed leaving 1,3,5,7 standing with the dagger in the hands of the 1st person. In the 2nd round, 1 will kill 3 and 5 will kill 7 and dagger is back in the hands of the 1st guy with number 5 as the only other person still standing. In the 3rd round, 1 will kill 5. Thus 1 will become the winner.
Now if the number of people is 100 initially, we let the activity or game proceed until the number of players alive reaches 2 to the power of some integer. Here we will wait until 100 reaches 64. Once it reaches 64, we know that the person whose turn it is to kill will win.
Now, the question is: whose turn is it when the number of people alive is 64.
Since 100 became 64, 36 people have died. These are numbers 2,4,6,8 etc till 72. And it's the turn of the 73rd person now. The number of people alive are all those from 73 to 100 (total 28) and those from 1,3,5,7 till 71 (total 36). 28+36=64.
Person number 73 will be the winner.
Interestingly if there are 2^n - 1 people in the circle, the last one will be the winner. If you are the 1st one, make sure there are 2^n people in the circle. If you are the last, make sure there are 2^n - 1 people. n is some positive integer.
No comments:
Post a Comment