48th 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 100000$ of this form is $N=2^{17}-2=131070$.