Anna and Berta are playing a game where they take marbles from the table in turns. 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
Every odd number is a winning situation because one can simply take all the marbles from the table.

The number 2 is a losing situation because only the move of 1 to 1 is allowed.

If an even number $2 \ell$ is a losing situation, then $2 \ell + 2j$ for $1 \leq j \leq \ell$ are winning situations: one can certainly remove $2j$ marbles from $2 \ell + 2j$ and reach the losing situation $2 \ell$.

If an even number $2 \ell$ is a losing situation, then $4 \ell + 2$ is also a losing situation: if one takes an odd number of marbles from $4 \ell + 2$, one reaches an odd number and thus a winning situation; even-numbered moves can only be 2, 4, ..., $2 \ell$, which, according to the previous consideration, also lead to an even winning situation.

Thus, we have determined all losing situations: they form the recursive sequence

$$
v_{m} = 2 v_{m-1} + 2, \quad m \geq 1
$$

with $v_{0} = 2$. This can be solved using standard methods or by adding 2 to both sides, i.e.,

$$
v_{m} + 2 = 2 (v_{m-1} + 2)
$$

with $v_{0} + 2 = 4 = 2^2$. By iteration, one sees immediately that $v_{m} + 2 = 2^{m+2}$, thus $v_{m} = 2^{m+2} - 2$.

We are looking for the smallest losing position $\geq 100000$, i.e., the smallest number of the form $2^{m+2} - 2 \geq 100000$. This is $2^{17} - 2 = 131070$.

(Clemens Heuberger)