Which number remains alive?

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

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

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

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

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