I have no idea on how to even attempt these;

First let J(n) be the number of people chosen

1 - Consider the case of an even number of people. Suppose initially there are 2n people. By considering the situation after n people have been removed, show that J(2n)=2J(n)-1 for all n>=1

2 - Then for odd number of people show that J(2n+1)=2J(n)+1 for all n>=1

3 - Prove by induction on m that J(2^m+l) = 2l + 1 for m>=0 and 0<=l<2^m (the inductive step you will need to consider the cases l even and odd separately)