there are n people, standing in a circle, first person have a gun, he kills the...?

Question

there are n people, standing in a circle, first person have a gun, he kills the the person standing next to him, and passes the gun to the next living man, the person who recieves the gun, does the same, this is continued till 1 person in the circle stays alive with a gun. i want to know the number of the last man who is alive with the gun.
example; n=5, first guy kills the 2nd one and passes the gun to the 3rd guy, 3rd kills 4th and 5th recieves the gun, 5th kills the 1st and 3rd recieves the gun, 3rd kills 5th, so 3rd survives.

Answer 1

I run this script on MatLab (replace the __ in front with spaces):
for n = 2:100; % try up to 100 people in the circle
__nn = [1:n]; % initiate all alive
__kk = find(nn); % set kk to be the indexes of those alive
__while length(kk) > 1; % more than one alive
____for ii = 2:2:length(kk); % Kill the next person and so on.
______nn(kk(ii)) = 0;
____end;
____if nn(kk(end))>0, % if the last person is not dead,
______nn(1) = 0; % then kill the first person
____end;
____kk = find(nn); % set kk to be the indexes of those alive
__end;
__ll(n-1) = kk; % record down the last survivor for each n value
end;
fprintf('%d %d\n', [2:length(ll)+1;ll]); % pring out the results.

Obviously, all even positioned people died in the first round.
Observations:
1) When n = powers of 2, person 1 survives.
2) When n is odd, person 3 survives.
3) When n/2 is odd, person 5 survives.
4) When n/4 is odd, person 9 survives.
5) When n/8 is odd, person 17 survives.
6) Deducing from 2) to 5), when n/2^k is odd, person 2^(k+1)+1 survives.

Someone free enough to derive this mathematically??

Answer 2

Throughout, let S(n) be the number of the person who survives in a round that starts with n people. We shall attempt to derive a recurrence relation for S(n)

Suppose we know the value of S(n). Imagine a round with 2n people. The first round consists of every even-numbered person being shot and the first person (who is effectively numbered 2n+1) receiving the gun again. There are now n people left - the first person is #1, the second person is #3, the third person is #5, and in general the kth person is #(2m-1). Since we now have a round with n people, it follows that the S(n)th person remaining will survive, and this was person 2S(n)-1 in the original numbering. So it follows that S(2n) = 2S(n) - 1

Next, imagine a round with 2n+1 people: as before, the shooting starts with all the even-numbered people being killed, but when the (2n-1)th person kills the (2n)th person, instead of handing the gun to number 1, he hands the gun to #(2n+1), who then shoots #1 and hands the gun to #3 (since #2 is dead). So at the end of this round, n even numbered people were killed, and #1 was killed, so there are n people remaining. The first person remaining is #3, the second is #5, the third is #7, and in general the kth person remaining is 2k+1. Since there are n people left, the S(n)th person will survive, and this is person 2S(n)+1. So S(2n+1) = 2S(n)+1.

Now, placing these figures into a proper recurrence relation, we know that if n is even, then S(n) = S(2(n/2)) = 2S(n/2) - 1, whereas if n is odd, S(n) = S((n-1) + 1) = S(2((n-1)/2)+1) = 2S((n-1)/2) + 1. Finally, we note that S(1) = 1, since the first guy has nobody to shoot, and so wins automatically. So we have:

S(n) = {2S(n/2) - 1 if n is even, 2S((n-1)/2) + 1 if n≥3 is odd, 1 if n=1}

Generating the first hundred values of S(n) reveals an interesting pattern:

1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, 7, 9, 11, 13,
15, 17, 19, 21, 23, 25, 27, 29, 31, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73

At each power of 2, person #1 wins, and between the powers of 2, each successive value increments the value of the winner by 2. So it seems that S(2^k+n) = 1+2n, provided that n<2^k. Let's see if we can prove this

First, the case where k=0. We need to show that for all n<2^0, that S(2^k+n) = 1+2n. Of course, there is only one possible value of n less than 1, and that is n=0. S(2^0 + 0) = S(1) = 1 = 1+2*0, so the formula holds whenever k=0.

Now, suppose the formula holds for some value of k. We want to show that for all n<2^(k+1), S(2^(k+1) + n) = 1+2n. We consider two cases. First, the case where n is even. Since n<2^(k+1), n/2<2^k, so we have by our inductive hypothesis that S(2^k + n/2) = 1+2(n/2). And since n is even, we have from the recurrence relation on S that S(2^(k+1) + n) = 2S(2^k + n/2) - 1 = 2(1+2(n/2)) - 1 = 2+2n - 1 = 1+2n, as required.

On the other hand, consider the case where n is odd. In that case, we definitely have that n-1<2^(k+1), so (n-1)/2 < 2^k, and by our inductive hypothesis we have that S(2^k + (n-1)/2) = 1+2((n-1)/2). So now by the recurrence relation on S, S(2^(k+1) + n) = 2S((2^(k+1) + n - 1)/2) + 1 = 2S(2^k + (n-1)/2) + 1 = 2(1+2(n-1)/2) + 1 = 2+2(n-1)+1 = 2+2n-2+1 = 1+2n, as required. So in either case, if the formula holds for all n<2^k for some value of k, then it also holds for all n<2^(k+1) for k+1. Thus by induction, it holds for all values of n and k where n<2^k.

So it follows from this that S(n) = 1 + 2(n-2^k), where 2^k is the largest power of 2 not greater than n. And we are done.

Answer 3

Hmmm there are some good answers based on mathematics. However they all ignore the obvious. If there's 2 men in the circle, there's no way the guy with the gun is going to give it up. Come to think of it most of these guys would have made a run for it long before the gun goes round the circle a first time.

Answer 4

n=2, s(survivor)=1 (2)
n=3, s=3 (2,1)
n=4, s=1 (2,4,3)
n=5, s=3 (2,4,1,5)
n=6, s=5 (2,4,6,3,1)
n=7, s=7 (2,4,6,1,5,3)
n=8, s=1 (2,4,6,8,3,7,5)
n=9, s=3 (2,4,6,8,1,5,9,7)
(killing sequence)

now we see some pattern here

when n = 2^x, s = 1
n = 2^x + y, s = 2y + 1

when n=5(in your example)
5=2^2+1
s=2*1+1=3

so when n=2^x + y
s=2y+1

edit
conclusion

n<2^x
s=2(n-2^x) + 1

edit 2nd time
my answer's right, but gotten that in an un-math way, i felt so bad bout it. i want another attempt at it.

it's clear to the eyes that for 2^x number of ppl playing(say paintball, coz violent is sooo not healthy, and i like colors, too!), or n=2^x, the 1st person always gets the gun in every starting of rounds.
1 round is cleared until you reach n. i mean, till all n who's playing has killed once or be killed(i wrote "has killed or be killed once". my grammar, poorly taught. and how many time the dead can be killed, though?) basically, all has either shot or dead.
after 1 round, 2^(x-1) ppls still "alive".
after (x-1) rounds, 2^(x-(x-1)) =2^1 =2 ppls still standing. in fact (s)he's the #1 and #[2^(x-1) +1] guy (simplified, guy #(n/2+1)).
#1 gets the gun first, again, shot #(n/2+1) and lives.

!!!points to see!!!
-->each round eliminate half the player.
-->and for n ppl playing, a survivor is the result of (n-1) deaths from (n-1) shot.
-->notice that for n=2^x, x rounds is needed to have one and only one survivor, with the last started with 2 guys, and exactly 1 killing left.

so we see, for n=2^x, survivor, s=1

then came the others who wanted to play, too. y many of them, in fact. but it's important to note that y<2^x, because when y=2^x, we'll always revert back to n=2^x+2^x=2*2^x=2^(x+1)=2^k where k=x+1.

now our n=2^x+y. in round 1, depending on even/odd of y, the last(#n) guy's life is at stake. if y=even, #n dies and #1 gets the gun as another round starts. if y=odd, #n lives, killing #1 instead.

in round 2, only 1 out of 4 will live on. since evens been eliminated, in 1-4 it's either #1 or #3 lives. and y as deciding factor, makes the call.
y=even, #4t-3 lives.(as in 2*(2k)-3)
y=odd, jersey #4t-1 lives.
(from 2*(2k+1)-3)

we've seen that y is the deciding factor for any # to live. because to live in the next round, you must be sure to survive the prior rounds. since y already "put life and death" decision as early as in the 2nd round, then y must have something to do with the players' survival at all.

we already have s=1 when n=2^x
but now that we have n=2^x+y as a general expression, and we know y is some big factor deciding survivor, then we conclude s=1 when y=0.
since we know s2(that is survivor of round 2)=2y-3
s(last survivor)=2y+m=1 at y=0
s=2*0+m=1, m=1

s=2y+1 for n=2^x+y when y<2^x
or s=2(n-2^x)+1

Answer 5

IS it 73?

Answer 6

that is depend on each person's LUCK. the most lucky person will survive