Austrian Mathematical Olympiad National Competition (Final Round, part 1)

We claim that the losing situations are those with exactly $n = 2^a - 2$ marbles left on the table for all integers $a \ge 2$. All other situations are winning situations.

Proof: By induction for $n \ge 1$. For $n = 1$ the player wins by taking the single remaining marble. For $n = 2$ the only possible move is to take $k = 1$ marbles, and then the opponent wins in the next move.

Induction step from $n-1$ to $n$ for $n \ge 3$:

1. If $n$ is odd, then the player takes all $n$ marbles and wins.

2. If $n$ is even but not of the form $2^a - 2$, then $n$ lies between two other numbers of that form, so there exists a unique $b$ with $2^b - 2 < n < 2^{b+1} - 2$. Because of $n \ge 3$ it holds that $b \ge 2$. Therefore all three numbers in this chain of inequalities are even, and therefore we can conclude that $2^b \le n \le 2^{b+1} - 4$. From the induction hypothesis we know that $2^b - 2$ is a losing situation, and by taking
$$k = n - (2^b - 2) = n - \frac{2^{b+1} - 4}{2} \le n - \frac{n}{2} = \frac{n}{2}$$
marbles we leave it to the opponent.

3. If $n$ is even and of the form $n = 2^a - 2$, then the player cannot leave a losing situation with $2^b - 2$ marbles to the opponent (where $b < a$ holds because at least one marble must be removed, and $b \ge 2$ holds because after a legal move starting from an even $n$, at least one marble remains). In order to do so, the player would have to remove $k = (2^a - 2) - (2^b - 2) = 2^a - 2^b$ marbles. But because of $b \ge 2$ we know that $k$ is even and strictly greater than $\frac{n}{2}$ because of $2^a - 2^b \ge 2^a - 2^{a-1} = 2^{a-1} > 2^{a-1} - 1 = \frac{2^a - 2}{2} = \frac{n}{2}$; impossible.

Solution: Berta can enforce a victory if and only if $N$ is of the form $2^a - 2$. The smallest number $N \ge 100\,000$ of this form is $N = 2^{17} - 2 = 131\,070$.