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