Which number remains alive?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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++;
    }
}

Answer 6

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

Answer 7

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.

Answer 8

Here is the solution in Python : Not an elegant mathematical one ; but since I did not know the mathematically

from itertools import cycle
NUMBER = 100
people = list(range(1, NUMBER + 1))
dead = []
print  "Runing"

print people
people_list = cycle(people)

while len(people) != 1:
    tolive = next(people_list)
    if tolive not in dead:
        todel = next(people_list)

    if todel not in dead:
        dead.append(todel)
    else:
        people = set(people) - set(dead)
        print sorted(people)
        people_list = cycle(sorted(people))

print people
print "over"

For 100 it is 73

Answer 9

this can be solved using mathematics of induction.

winner=(total_people - (2^i - 1 - total_people))

here i can be calculated using this equation:

2^i <= total_people < 2^(i+1)

Here's the c++ implementation:

#include<iostream>
#include<cstdio>
#include<math.h>

using namespace std;

int main(void)
{
    int i,total_people;

    while(true){
        cin>>total_people;
        i=0;
        while(pow(2,i)<=total_people){
            i++;
        }
        i--;
        int winner=(total_people-(pow(2,i+1)-1-total_people));
        cout<<winner;

    }

}

Answer 10

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

$${}$$