1000 people in a circle

[Guest]

1000 people are standing in a circle, all numbered from 1 to 1000.

Person 1 has sword with which he kills person 2 gives the sword to person 3.

Person 3 kills person 4 and passes the sword to person 5.

Every time the person who has the sword kills the next person in the circle and passes the sword.

This is continued till there is only one person alive.

Who is the Last Man Standing?

Spoiler

Person : 977

Can you derive a general formula and also a general method for any value of initial number of person.

[Guest]

Unless I've done my bookkeeping wrong (that has happened sometimes...)

This is a specific case of the Josephus Ring, and I don't remember there being a closed form expression. However, with the example of skipping exactly one person, maybe there's a special case. (And, maybe I don't remember right)

1 kills 2

3 kills 4...

999 kills 1000

now we have 1-999 by 2s (4n+1 will survive)

1 kills 3

5 kills 7...

997 kills 999

now we have 1-997 by 4s (8n+1 will survive)

1 kills 5

9 kills 13...

993 kills 997

now we have 1-993 by 8s (16n+1 will survive)

1 kills 9

17 kills 25...

993 kills 1

now we have 17-993 by 16s (32n+17 will survive)

17 kills 33

49 kills 65...

977 kills 993

now we have 17-977 by 32s (64n+17 will survive)

17 kills 49

81 kills 113...

977 kills 17

now we have 81-977 by 64s (128n+81 will survive)

81 kills 145

209 kills 273...

977 kills 81

now we have 209-977 by 128s (256n+209 will survive)

209 kills 337

465 kills 593 ...

977 kills 209

now we have 465-977 by 256s (512n+465 will survive)

(465, 721, 977)

465 kills 721

977 kills 465 and is the sole survivor

I agree with CaptainEd.

This is a little complicated so I'll make it in steps. I'll use n=1000 people for the example.

1. Take the log base 2 of n. [log2(1000) = 9.9658]

2. Round the answer down to the nearest integer (We will call this a) [ 9.9658 -> 9]

3. Find 2^a. [2^9 = 512]

4. Divide n by that result and get the remainder [1000/512 = 1 remainder 488]

5. Survivor = 2*remainder+1 [2*488+1 = 977]

I'm sure there is an easier way to write a general formula for this. This is just what I came up with real quick.

[fritzb]

Assuming N people, the last standing (S) is given by: S=2*(N-2^m)+1, where m=floor[ln(N)].

[plasmid]

This is definitely not the most eloquent proof ever, but...

Define S(n) as the solution to the problem if you have n swordsmen. That is, you're asking us to find S(1000).

Suppose n is even. Then after one round, all of the even numbered people would be dead and you would have swordsman #1 holding the sword again. The remaining people would be numbered {1, 3, 5, 7, ...} and the size of the group would be n/2. So, if you knew what S(n/2) was, then you could figure out what S(n) was. Suppose S(n/2) was person #3: then looking at the set above, we would see that the person who was #3 in the group of size n/2 would have been person #5 in the group of size n. In general, person #i in the small group would have been person #(2i-1) from the big group. So S(n) = S(n/2) x 2 - 1. Remember, all this is assuming that n is even.

Suppose n is odd. Then after one round, all of the even numbered people will still be dead, and as the last (odd numbered) person takes the sword he will kill #1 and person #3 will start off with the sword on the next round. The remaining people will be numbered {3, 5, 7, 9, ...} and the size of the group would be (n-1)/2. So this time, if you knew what S(n/2-1) was, you could figure out what S(n) was. Person #i in the small group would have been person #(2i+1) from the big group. So S(n) = S([n-1]/2) x 2 + 1. That's if n is odd.

Now take the case of S(1000)

S(1000) = S(500) x 2 - 1

S(500) = S(250) x 2 - 1

S(250) = S(125) x 2 - 1

S(125) = S(62) x 2 + 1

S(62) = S(31) x 2 - 1

S(31) = S(15) x 2 + 1

S(15) = S(7) x 2 + 1

S(7) = S(3) x 2 + 1

S(3) = S(1) x 2 + 1

S(1) = 1 (obviously)

So, S(3)=3, S(7)=7, S(15)=15, S(31)=31, S(62)=61, S(125)=123, S(250)=245, S(500)=489, S(1000)=977

Now to simplify that some to make this a general case solution. It would actually be easier if we write the numbers in binary, like S(11001).

Doubling any binary number is done by simply adding a zero to the end (just like multiplying by 10 in base 10). So if you know S(11001), then S(110010) = S(11001) x 2 - 1.

Likewise, multiplying by two and adding one is done by simply adding a one to the end, so if you know S(11001), then S(110011) = S(11001) x 2 + 1.

Now for any number we can start building it from S(1)=1. To get to S(11001) we would do:

S(1) = 1

S(11) = S(1)x2+1 = (in binary) (1)x2+1 = 10+1 = 11

S(110) = S(11)x2-1 = (in binary) (11)x2-1 = 110-1 = 101

S(1100) = S(110)x2-1 = (in binary) (101)x2-1 = 1010-1 = 1001

S(11001) = S(1100)x2+1 = (in binary) (1001)x2+1 = 10010+1 = 10011

Notice what's happening: S(n) will always end in a 1 at the rightmost spot (er, be odd). That's because it's always calculated as S(previous)x2+1 or S(previous)x2-1.

Adding a 0 to the end of the n in S(n) entails performing the operation S(n)x2-1 on an odd binary number, call it abcde...xyz1. Doubling it gives you abcde...xyz10, and then subtracting 1 from it makes it abcde...xyz01. It's exactly the same as putting a zero in the next-to-last spot.

On the other hand, adding a 1 to the end of the n in S(n) entails performing the operation S(n)x2+1. In binary, multiplying by two and adding 1 is just the same as adding a 1 to the end of the number. Using the notation above, abcde...xyz1 goes to abcde...xyz11, you could also say it's the same as adding a 1 to the next-to-last spot.

Now consider the arbitrary number S(1abcdefg) where abcdefg are binary digits

S(1) = 1

S(1a) = a1

S(1ab) = ab1

S(1abc) = abc1

etc.

Since 2^n in binary is 100000... with n zeros, MGH's step 4 of taking the remainder after dividing by the largest available 2^n is just the same as removing the leading 1, leaving you with the abcdefg

Then MGH's step 5 of multiplying by 2 and adding one is the same as adding 1 to the end of the binary number, giving you abcdefg1, the solution above.

(Jeez that was tough. Good problem.)

[Guest]

Congratulations guys you got it correctly .....

General case when there are n person standing in a circle.

Lemma 1 : If n = 2^k then the last man standing is the person which carries the sword initially.

In this case its person number 1. (See proof below)

Lemma 2 : In first round after x (x < n/2) person have been killed the sword is with 2x+1 person.

Now when n is not equal to 2^k then we can write n = 2^q + a, where a < 2^q .

Now as soon as a people are killed, there are 2^q person left in the circle and now the sword is with person no 2a+1 (from lemma 2).

So from lemma 1 we can say that the last man standing will be person number 2a+1.

where , a = n -2^q

Now since, 2^q < n < 2^q+1

taking log and solving for q we get,

q = floor(log₂ n)

that is the general formula.

Proof of Lemma 1 :

It can be proved via induction.

whenever there are even number of person ,then after round 1, the person 1 will get back the sword.

To prove : If n = 2^k then the last man standing is the person which carries the sword initially.

In this case its person number 1.

for n=1 it is trivial..

assume it is true for n = m

for n = m+1 ,total number of person = 2^m+1 .(an even number)

So, after the first round,there are 2^m person left and the sword will be with person number 1.

which reduces to the case of 2^m person that we had already assumed to be true.

Hence the lemma is proved.

[Tinku VNCK]

I tried in this way using the formula of a guest

logarithm of 1000 base 2 = 9.9~10

2^10 = 1024

now of soldiers = 1000

1000-1024=-24

solider at 24th position in anti clock wise direction survives

that is 1000-24+1=977

I tried in this way using the formula of a guest

logarithm of 1000 base 2 = 9.9~10

2^10 = 1024

now of soldiers = 1000

1000-1024=-24

solider at 24th position in anti clock wise direction survives

that is 1000-24+1=977

[CaptainEd]

1 kills 2

3 kills 4...

999 kills 1000

now we have 1-999 by 2s (4n+1 will survive)

1 kills 3

5 kills 7...

997 kills 999

now we have 1-997 by 4s (8n+1 will survive)

1 kills 5

9 kills 13...

993 kills 997

now we have 1-993 by 8s (16n+1 will survive)

1 kills 9

17 kills 25...

993 kills 1

now we have 17-993 by 16s (32n+17 will survive)

17 kills 33

49 kills 65...

977 kills 993

now we have 17-977 by 32s (64n+17 will survive)

17 kills 49

81 kills 113...

977 kills 17

now we have 81-977 by 64s (128n+81 will survive)

81 kills 145

209 kills 273...

977 kills 81

now we have 209-977 by 128s (256n+209 will survive)

209 kills 337

465 kills 593 ...

977 kills 209

now we have 465-977 by 256s (512n+465 will survive)

(465, 721, 977)

465 kills 721

977 kills 465 and is the sole survivor

Unless I've done my bookkeeping wrong (that has happened sometimes...)

This is a specific case of the Josephus Ring, and I don't remember there being a closed form expression. However, with the example of skipping exactly one person, maybe there's a special case. (And, maybe I don't remember right)

Edited April 14, 2009 by CaptainEd

[Guest]

Person 1 is left behind there would be no one to kill him

[CaptainEd]

I agree with CaptainEd.

This is a little complicated so I'll make it in steps. I'll use n=1000 people for the example.

1. Take the log base 2 of n. [log2(1000) = 9.9658]

2. Round the answer down to the nearest integer (We will call this a) [ 9.9658 -> 9]

3. Find 2^a. [2^9 = 512]

4. Divide n by that result and get the remainder [1000/512 = 1 remainder 488]

5. Survivor = 2*remainder+1 [2*488+1 = 977]

I'm sure there is an easier way to write a general formula for this. This is just what I came up with real quick.

MGH, that's Marvelous! Why/how does it work?

[Guest]

MGH, that's Marvelous! Why/how does it work?

Not sure I can tell you exactly why it works but I can tell you how I came up with it. I started by looking for a pattern. First off, you find out real quick that the even people get waxed on the first round. I then checked the outcome for 1 to 20 people (it took a while). I noticed that when n (the total number of people) equals a power of 2 (i.e, 2, 4, 8, 16), then the first person is always the last man standing. Here is a list of the survivor for 1 to 20 people:

n survivor

1 1

2 1

3 3

4 1

5 3

6 5

7 7

8 1

9 3

10 5

11 7

12 9

13 11

14 13

15 15

16 1

17 3

18 5

19 7

20 9

Once I saw this I was able to craft the "formula" to spit out the survivor based on any number of people. I wish I could say I used some clever method to get the formula, but I pretty much just kept looking till I found a way for it to work out.

If you look at it you do see that the formula does make sense. Take the case where n is a power of 2, say 16. On the first round of killings, all the even people are killed. You end up with a spacing of 2 in between all the survivors (i.e. 1,3,5,7,9...). Then after the second round, you end up with a spacing of 4 (1,5,9,13). Then after the third round you get a spacing of 8 (1,9). If we had used a very large power of 2 for n, then you would see that the spacings keep incrementing each round by a power of 2 (2,4,8,16,32,...). Also, if the total number of people is not a power of 2, then the spacings are still there, except there is an offset. I just used these patterns to come up with something that worked. I'm sure someone better at math could explain it better.

Mike

[plasmid]

Congratulations guys you got it correctly .....

General case when there are n person standing in a circle.

Lemma 1 : If n = 2^k then the last man standing is the person which carries the sword initially.

In this case its person number 1. (See proof below)

Lemma 2 : In first round after x (x < n/2) person have been killed the sword is with 2x+1 person.

Now when n is not equal to 2^k then we can write n = 2^q + a, where a < 2^q .

Now as soon as a people are killed, there are 2^q person left in the circle and now the sword is with person no 2a+1 (from lemma 2).

So from lemma 1 we can say that the last man standing will be person number 2a+1.

where , a = n -2^q

Now since, 2^q < n < 2^q+1

taking log and solving for q we get,

q = floor(log₂ n)

that is the general formula.

Proof of Lemma 1 :

It can be proved via induction.

whenever there are even number of person ,then after round 1, the person 1 will get back the sword.

To prove : If n = 2^k then the last man standing is the person which carries the sword initially.

In this case its person number 1.

for n=1 it is trivial..

assume it is true for n = m

for n = m+1 ,total number of person = 2^m+1 .(an even number)

So, after the first round,there are 2^m person left and the sword will be with person number 1.

which reduces to the case of 2^m person that we had already assumed to be true.

Hence the lemma is proved.

Neat! Much more elegant proof, hardly uses any math at all (which is a good thing).

[bonanova]

Great puzzle from the past, resurrected by TinkuVNCK.

Because the OP seems to have left the forum, I'm 

• marking mghoffman78 as first solver
• upvoting plasmid for heroic calculation of the answer
• upvoting guru_bhai for an "elegant proof"
• upvoting TinkuVNCK for a cute, quick-and-dirty algorithm
• upvoting fritzb for a nice closed form solution

Good work all.

[plasmid]

I think I prefer this wording instead of a formula (even if I didn't explicitly word it this way back when I did the proof)

Spoiler

Write the number in binary, then move the leading 1 from the front of the binary number to the end, and that's your answer.

 

[leif573]

On 4/14/2009 at 12:44 PM, Guest said:

 

 

I agree with CaptainEd.

 

 

Hidden Content

How HOWBTHE f*** IN GODS NAME WOULD ANYONE COME UPNWITHBTHIS FORMULA..I DONT SEE HOW ANYONE WOHLD EVER..and I'm a math genius..this is impossible npossible..I did it by t=ial and error..surely this is how you would and most math geniuses like me would..

[leif573]

On 4/14/2009 at 8:16 PM, plasmid said:

 

Neat! Much more elegant proof, hardly uses any math at all (which is a good thing).

How in God's name could or would anyone come up with a general formula like this?? I don't see how and I'm a math g÷nous..I don't see how anyone could..seriosuly..whybdoes math have to be so ridiculous and frustrating sometimes..no one would ever think lf this..hope you can respond..

[leif573]

On 2/14/2017 at 5:32 PM, Tinku VNCK said:

I tried in this way using the formula of a guest

logarithm of 1000 base 2 = 9.9~10

2^10 = 1024

now of soldiers = 1000

1000-1024=-24

solider at 24th position in anti clock wise direction survives

that is 1000-24+1=977

I tried in this way using the formula of a guest

logarithm of 1000 base 2 = 9.9~10

2^10 = 1024

now of soldiers = 1000

1000-1024=-24

solider at 24th position in anti clock wise direction survives

that is 1000-24+1=977

Why would you think of that thiugh..what donyou mean anticlockwise..I don't see why ANYONE would EVER THINK of that..how do you know tonadd 1..because the last term 1000 is out innthe first round??