Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are $100$ people standing in a circle numbered from $1$ to $100$. The first person is having a sword and kills the the person standing next to him clockwise i.e $1$ kills $2$ and so on. Which is the last number to remain alive? Also if $1$ kills both the person standing next to him. Which is the last number standing? Can both of them be generalized?

share|improve this question
12  
If $1$ kills $2$, how can $2$ kill $3$?? $2$ is dead! –  Ishfaaq Aug 12 at 9:16
1  
i think it is spiritual question :D :D :D –  dato datuashvili Aug 12 at 9:18
4  
3 kills 4, 5 kills 6...goes on till one orperson is left –  user2131465 Aug 12 at 9:18
7  
but main question is where is police :D –  dato datuashvili Aug 12 at 9:19
4  
The barbaric Josephus problem. –  Hat Man Aug 12 at 9:41

9 Answers 9

The first case is similar to Josephus Problem and in general situation, we can use the following MATLAB code to get the remaining number:

First Case:

function RemainNum = JosephusProblem(n,m)
A = 1:n;
A = A';
for k = 1:n-1
  A = circshift(A,length(A)-mod(m+1,length(A)) + 1);
  A = A(1:(end-1));
RemainNum = A;

where $n$ is the total number of person in this circle and from the person #1, people count number one by one from 1 to $m$ circularly and the person who tells the number $m$ gets killed and this process doesn't end until there is only one person left, then the function returns this lucky guy by $\text{RemainNum}$. So in this case, $m=2$. People count like $1,2,1,2,...$ and persons who count 2 get killed.

Second Case:

Let $f(n)$ be the lucky number in this case, then I guess that $$f(n) = \begin{cases} 1, &\text{if $n=1$}\\ n-1, & \text{if $n$ is even} \\ n-2, & \text{if $n$ is odd} \\ \end{cases}$$ Since every time at most 2 persons are killed and 1 person is killed only when there are only 2 person left, so when $n$ is even, finally there will be only 2 persons left after $\frac{n-2}{2}$ times killing and person $n-1$ gets the sword, so $f(n) = n-1$ in this case. When $n$ is odd, after $\frac{n-3}{2}$ times killing, there will be 3 person left, and person $n-2$ gets the sword and then kills the other two, so $f(n)= n-2$ in this case.

share|improve this answer
    
MathJax wasn't made for code. In Markdown, we use backticks (`code`) for inline code snippets, and four spaces (<newline> code) for "separate" code. See my edit. –  Giulio Muscarello Aug 12 at 13:59
    
Thanks a lot!@Giulio Muscarello –  Peida Tian Aug 12 at 14:00
    
Oh yeah...Josephus problem. I remember the implementation in C using Linked List. –  MonK Aug 12 at 14:28
    
Yes, we can use linked list in C and we can also use only array to implement it. In MATLAB, the implementation can be very simple. –  Peida Tian Aug 12 at 14:35

First case : If 1 kills 2, then 2 can not kill 3 because he is dead. So we are down to every odd number killing the even numbered person. So, Updating after @coffeemath's comment

After 1st round: $$1,3,5,7,9\cdots99$$ 2nd round:$$1,5,9,13\cdots97$$ 3rd round:$$1,9,17,25\cdots97$$ 4th round:$$9,25,41,57,73,89$$ 5th round:$$9,41,73$$ 6th round:$$9,73$$

And 73 kills 9 ultimately. :)

To calculate I used an excel sheet and started to mark people alive after 1st round,2nd round and so on.

Second Case: 100 is standing next to 1, because they are standing in circle. So, 1 kills 2 and 100 (both even). 3 kills both 1 and 4, cos 1 is alive and next to 3 now and this goes on. So, the sequence

$$\begin{align}\\ 1-100,2\\3-1,4\\5-3,6\\7-5,8\\9-7,10\\...\\...\\99-97 \end{align}$$

There is no one to kill 99. So 99 is alive. :)

share|improve this answer
    
Hey! Thanks, but can we generalize it? –  user2131465 Aug 12 at 10:07
    
No, you can't, unfortunately. But I think you can definately write a program for both the cases. –  MonK Aug 12 at 10:19
1  
99 has just killed 100, so now the sword passes to 1. Thus 1 stays alive after the first "round", and then 3,7 etc get killed next. –  coffeemath Aug 12 at 10:34
    
yes, you are right, updating. thanks –  MonK Aug 12 at 10:45
    
The latter one does appear to generalize, at least for even numbers of people. 1 will always kill 2 and n, and everyone will kill the person behind them, leaving no one to kill n-1. For odd n, it appears to be n-2 who survives. –  trlkly Aug 12 at 17:51

Write it in binary and shift (with cyclic rotation) one bit left - ;-) The closed formula is: $$ f(n) = 2 \cdot ( n - 2^{\lfloor log_2n \rfloor}) + 1 $$

More details could be found in Concrete Mathematics by Donald Knuth, chapter 1.3.

share|improve this answer

This is for the first case, where killing proceeds only clockwise. Let $f(n)$ be the position of the last person alive. Then we can show two recursive statements to determine $f(n)$ (given the initial $f(1)=1$): $$f(2n)=2f(n)-1, \\ f(2n+1)=2f(n)+1.$$ For the $f(2n)$ case, the remaining numbers after one round are $2\cdot 1-1,\cdots 2n-1.$ (and the $1$ is alive on the next round) This is a list of $n$ numbers $2k-1,$ with $1 \le k \le n$ So if we know the value of $f(n)$ we can just adjust it to where it is on this list, and get $2f(n)-1$ for $f(2n).$

For the $f(2n+1)$ case, one round again kills the even indexed values, but the last position $2n+1$ now holds the sword and will then kill $1$, so that we are left with the numbers of the list $2\cdot 1+1, \cdots, 2n+1$ (with the $3$ alive) which is again a list of $n$ numbers, so that similarly to the above if we know $f(n)$ we can adjust it to where it is on this list to get $2f(n)+1$ for the value of $f(2n+1).$

Applying these recursions to $f(100)$ we have $$f(100)=2f(50)-1,\\ f(50)=2f(25)-1,\\ f(25)=2f(12)+1,\\ f(12)=2f(6)-1,\\ f(6)=2f(3)-1,\\ f(3)=2f(1)+1.$$ Then plugging in $f(1)=1$ and working upward gives $f(100)=73$ (as in MonK's answer).

These recursions would give $f(n)$ for any $n$ but aren't in a closed form, which would be nicer.

Added: By looking at $n$ in base 2 and using the above recursions, one can get the following "almost" closed form. If $2^k \le n < 2^{k+1}$ then $$f(n)=2(n-2^k)+1.$$ In particular $f(n)$ must be odd in all cases, something unexpected (to me). This form is another version of the one cited by fex in his answer above, from Knuth.

share|improve this answer
    
Actually that $f(n)$ is odd is clear since in round one all the evens get killed, for any $n.$ –  coffeemath Aug 13 at 21:11

ok because $1$ kill $2$ ,then $3$ kill $4$,that means that we have odd numbers after one round

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
75
77
79
81
83
85
87
89
91
93
95
97
99

now we are continuing again or ?after another round we have these numbers

1

5

9

13

17

21

25

29

33

37

41

45

49

53

57

61

65

69

73

77

81

85

89

93

97

final result is 73

share|improve this answer
    
Yes! It continues till 1 person is left. –  user2131465 Aug 12 at 9:33
    
next stage 1 kills 3,5 kills 7,7 kills 9 and so on right –  dato datuashvili Aug 12 at 9:34
1  
99 kills 100 now the sword is with 1, and now 3, 7, 11...are dead and it continues. –  user2131465 Aug 12 at 9:37
2  
en.wikipedia.org/wiki/Josephus_problem please look on this problem –  dato datuashvili Aug 12 at 9:45
1  
Too good, this is what I wanted. Thank you so much...:) –  user2131465 Aug 12 at 10:07

Last Survival is 61 as shown in below matrix

1st 2nd 3rd 4th 5th Final Round

1 1 1 5 13 29 61
2 3 5 13 29 61
3 5 9 21 45 93
4 7 13 29 61
5 9 17 37 77
6 11 21 45 93
7 13 25 53
8 15 29 61
9 17 33 69
10 19 37 77
11 21 41 85
12 23 45 93
13 25 49
14 27 53
15 29 57
16 31 61
17 33 65
18 35 69
19 37 73
20 39 77
21 41 81
22 43 85
23 45 89
24 47 93
25 49 97
26 51
27 53
28 55
29 57
30 59
31 61
32 63
33 65
34 67
35 69
36 71
37 73
38 75
39 77
40 79
41 81
42 83
43 85
44 87
45 89
46 91
47 93
48 95
49 97
50 99
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

$${}$$

share|improve this answer
    
Hi and welcome to Math SX! Please remember to use markup to format/align your answers! –  MattAllegro Aug 30 at 8:03

Second case if we have m guys at the table:

survivor = m-($m\pmod2$)-1

$1->m,2$

(for 0$<$n$<$(m-2)/2)

$2*n+1$$->$$2*n-1$,$2*n+2$

then the last guy kill someone is $(m-1)->(m-3)$ or $(m-2)->(m-1),(m-4)$ and from there because of its value depends on modulo 2, $survivor = m-($$m\pmod2$$)-1$.

First case if we have m guys at the table:

$n=floor(\log_{2}m)$

$survivor = 2*(m-2^n)+1$

if length is even

$a->a+k,a+2*k->a+3*k,..,a+(n-1)*k->a+n*k$

$a,a+2*k,a+4*k,..,a+(n-1)*k$

if length is odd

$a->a+k,a+2*k->a+3*k,..,a+(n-2)*k->a+(n-1)*k,a+n*k->a$

$a+2*k,a+4*k,a+6*k,..,a+n*k$

If we always make length half and survivor changes only $\pmod2$ is equal to 1 then I thought if we thought that number as a binary then the digits which are zero is make survivor less then the m is $m-binaryInverse(m)$ is equal to survivor then it is same with $survivor = 2*(m-2^n)+1$. Sorry for my english but i try to make it better.

share|improve this answer
    
Please use MathJax to format your answer. –  MonK Aug 13 at 9:36
    
Please can you explain how you arrived? –  Alizter Aug 13 at 9:40

Here's my solution, in C. The answer is 73.

#include <stdio.h>
#define N 100
void main(){
    int i=0, j; //i has the sword, j gets killed.
    int a[N]={0}; //0=not killed
    while(1){
        if(i != N-1) j = i + 1;
        else j = 0;
        while(a[j])
            if((j + 1) == N) j = 0; //loop back to 0
            else j++; //skip over the killed people
        if(i==j){ //if i is the only one left, stop
            printf("\n\n\n%d is left!", i+1);
            return;
        }
        a[j] = 1; //kill j
        printf(" %d kills %d.", i+1, j+1);
        if(j != N-1) i = j + 1;
        else i=0;
        while(a[i])
            if((i + 1) == N) i = 0;
            else i++;
    }
}
share|improve this answer

1 kills 2 ... 3 kills 5... in the process 1 is alive till 99 kills 100 and passes it back to 1. 1 kills 99 and 1 is ALIVE

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.