Q: Removing numbers skipping one at a time We have numbers from $1$ to $n$. We start with $1$. We remove it, then skip the next number ($2$) and remove the next one ($3$). We keep doing this until we get to the end. Then we go back to the start, remove the first number remaining and then skip the next remaining number and remove the one after that. What is the last number we remove?
For example, take $n=30$. Then, in the first "round", we remove all the odd numbers. Then in the second round, we remove $2$, $6$, $10$, etc. all the way up to $30$. Here's how it goes:
$1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29$
$2, 6, 10, 14, 18, 22, 26, 30$
$4, 12, 20, 28$
$8, 24$
$16$
I realized that each round starts with the next power of two and that the largest power of two smaller than $n$ is the last number we remove. However, I don't really understand why.

A: It's a little easier to consider the numbers that remain after each round. After the first round you have the even numbers less than or equal to $n$. After the second round you have the multiples of $4$ less than or equal to $n$. After the third round you have the multiples of $8$ less than or equal to $n$. A bit of experimentation should convince you that after the $k$-th round you have the multiples of $2^k$ less than or equal to $n$; this can be proved by induction on $k$.
Now suppose that $2^m$ is the largest power of $2$ that is less than or equal to $n$. Then $2^m$ is the only multiple of $2^m$ less than or equal to $n$, so after $m-1$ rounds it will be the only number left and will therefore be the last number removed.
