Guest Posted April 14, 2009 Report Share Posted April 14, 2009 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. Quote Link to post Share on other sites

0 CaptainEd 26 Posted April 14, 2009 Report Share Posted April 14, 2009 (edited) 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 Quote Link to post Share on other sites

0 Guest Posted April 14, 2009 Report Share Posted April 14, 2009 Person 1 is left behind there would be no one to kill him 1 Quote Link to post Share on other sites

0 Solution Guest Posted April 14, 2009 Solution Report Share Posted April 14, 2009 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. Quote Link to post Share on other sites

0 CaptainEd 26 Posted April 14, 2009 Report Share Posted April 14, 2009 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? Quote Link to post Share on other sites

0 Guest Posted April 14, 2009 Report Share Posted April 14, 2009 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 Quote Link to post Share on other sites

1 plasmid 41 Posted April 14, 2009 Report Share Posted April 14, 2009 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.) Quote Link to post Share on other sites

1 Guest Posted April 15, 2009 Report Share Posted April 15, 2009 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_{2 }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. Quote Link to post Share on other sites

0 plasmid 41 Posted April 15, 2009 Report Share Posted April 15, 2009 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_{2 }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). Quote Link to post Share on other sites

1 Tinku VNCK 0 Posted February 14, 2017 Report Share Posted February 14, 2017 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 Quote Link to post Share on other sites

2 fritzb 1 Posted February 15, 2017 Report Share Posted February 15, 2017 Assuming N people, the last standing (S) is given by: S=2*(N-2^m)+1, where m=floor[ln(N)]. 1 Quote Link to post Share on other sites

0 bonanova 85 Posted February 25, 2017 Report Share Posted February 25, 2017 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. Quote Link to post Share on other sites

0 plasmid 41 Posted March 2, 2017 Report Share Posted March 2, 2017 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. Quote Link to post Share on other sites

## Question

## 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?

## Link to post

## Share on other sites

## 12 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.