• 0
Sign in to follow this  
Followers 0

Question

Posted · Report post

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?

Person : 977

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

0

Share this post


Link to post
Share on other sites

8 answers to this question

  • 0

Posted (edited) · Report post

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 by CaptainEd
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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?

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.)

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

Congratulations guys you got it correctly .....

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

Lemma 1 : If n = 2k 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 2k then we can write n = 2q + a, where a < 2q .

Now as soon as a people are killed, there are 2q 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 -2q

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

taking log and solving for q we get,

q = floor(log2 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 = 2k 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 = 2m+1 .(an even number)

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

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

Hence the lemma is proved.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

Congratulations guys you got it correctly .....

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

Lemma 1 : If n = 2k 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 2k then we can write n = 2q + a, where a < 2q .

Now as soon as a people are killed, there are 2q 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 -2q

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

taking log and solving for q we get,

q = floor(log2 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 = 2k 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 = 2m+1 .(an even number)

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

which reduces to the case of 2m 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).

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0

  • Recently Browsing   0 members

    No registered users viewing this page.