AT-OEMO-FED1 2017 Problem 3

Anna and Berta play a game in which they take turns in removing marbles from a table. Anna takes the first turn. At the beginning of a turn there are n ≥ 1 marbles on the table, then the player whose turn is removes k marbles, where k ≥ 1 either is an even number with $k \le \frac{n}{2}$ or an odd number with $\frac{n}{2}\le k \le n$ . A player wins the game if she removes the last marble from the table. Determine the smallest number $N\ge100000$ which Berta has wining strategy.

proposed by Gerhard Woeginger