This is one more interesting problem - there are n persons standing forming a circle. The first person has a sword, he kills 2nd person and hands over the sword to the 3rd person. He kills 4th and gives it to 5th and so on... (Remember that these persons are in circle, so if last person gets the sword, he will kill 1st.)
Problem is - given the value of n, find out the person who will survive.
Scroll down to find the solution to this problem, but I urge to take some time to solve this one - Thats where the fun is :)
To solve this problem, I divided the problem in two parts. Lets take the case when n is even and then think about the odd n.
I also wrote a small python program to see the result and then try to map these results with some known series like fibonacci etc.
I am pasting my code here -
mylist = []j = input("Enter the last number upto which we need to calculate this: \n")#Add valuesfor i in range(1,j+1): mylist.append(i)num = 1while len(mylist) != 1: del mylist[num] num = (num + 1) % len(mylist)print "\n And the no. remaining is : ", mylistWith this, I came to know that if n is even, result is always 4x+1.
If n is odd, result follows 4x+3.
But I couldn't get any relation between x and n.
Then I realized one more phenomena - no matter if n is even or odd. There is some relation in n and the next no. which is power of 2.
Take n = 1000. (result is 977.)
next no which is power of 2 = 1024.
difference = 1024-1000 =24
subtract 24 from 1000 = 976.
Add 1 = 977. (We have the answer).
Lets try odd n.
let n = 999.
next no. which is power of 2 = 1024.
1024-999 = 25.
999-25+1 = 975 - which is the real answer!!!
I won't give more example here, but I tried more and they were all matching up.
One of my friends suggested that if I convert the no. to binary and then add all powers of 2 where 1 occurs and add all powers of 2 where 0 occurs and then subtract the two, I have the answer.
e.g. take 5 = 101.
1's are on 0th and 2nd position - add them 2^0+2^2 = 5.
0's are on 1st position - add them 2^1 = 2
subtract both 5-2 =3 - this is our answer.
On further thinking, adding 1's is not necessary as it will always result in the no. itself. :)
Labels: puzzles