Anna and Berta are playing a game where they take turns removing marbles from the table. Anna makes the first move. If at the beginning of a turn there are $n \geq 1$ marbles on the table, then the player whose turn it is takes $k$ marbles, where $k \geq 1$ is either an even number with $k \leq \frac{n}{2}$ or an odd number with $\frac{n}{2} \leq k \leq n$. A player wins the game if they take the last marble from the table.

Determine the smallest number $N \geq 100000$ such that Berta can enforce a win if there are exactly $N$ marbles on the table at the start.

(Gerhard Woeginger)

![](https://cdn.mathpix.com/cropped/2024_04_17_2ff2d8d0a79f0eb08e64g-5.jpg?height=1085&width=1060&top_left_y=100&top_left_x=498)

Figure 2: Solution 3
Claim: The losing situations are those with $n=2^{a}-2$ marbles on the table for all integers $a \geq 2$. All other situations are winning situations.

Proof: By induction over $n \geq 1$. For $n=1$, you win by taking the only remaining marble. For $n=2$, you can only take $k=1$ marble, and then your opponent wins on the next turn.

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

1. If $n$ is odd, take all $n$ marbles and win.
2. If $n$ is even but not of the form $2^{a}-2$, then $n$ lies between two numbers of this form, so there is a unique integer $b$ with $2^{b}-2 < n < 2^{b+1}-2$. In this case, you can take $k = n - (2^{b}-2)$ marbles, leaving $2^{b}-2$ marbles on the table, which is a losing situation for your opponent. If $n$ is of the form $2^{a}-2$, then any number of marbles you take, $k$, will leave a number of marbles that is not of the form $2^{a}-2$. Specifically, if you take $k$ marbles, the number of marbles left is $n - k = 2^{a}-2 - k$. For $k$ to be a valid move, $1 \leq k \leq \frac{n}{2} = 2^{a-1}-1$. If $k = 2^{a-1}-1$, then $n - k = 2^{a-1}-1$, which is not of the form $2^{a}-2$. For any other $k$, $n - k$ will also not be of the form $2^{a}-2$. Therefore, your opponent will always be left with a winning situation.

Solution to the problem: Berta can force a win if and only if $N$ is of the form $2^{a}-2$. The smallest number $N \geq 100000$ of this form is $N=2^{17}-2=131070$.

(Gerhard Woeginger)