You are playing the following two-person pebble game. Initially there are $n$ pebbles. Each turn, if there are $k$ pebbles remaining then the current player may take up to $\left\lfloor{\frac{k-1}{2}}\right\rfloor$ pebbles. The first person who can’t take any more pebbles loses.
If you go first in this game, for which $n$ do you have a winning strategy?
For this question, I am focusing on the cases when $k = 1, 2$, then that is a loss for the player. And I want to leave these cases to the opponent.
Now I discovered that for $n = 3, 5, 6$, I can win the game. But I am wondering what other options do I have, and also if there is a pattern in the selection of $n$. Thank you.
The numbers of pebbles can be divided into $N$ positions, which are wins for the next player, and $P$ positions, which are wins for the previous player. An $N$ position is one that can move to some $P$ position. A $P$ position is one that can only move to $N$ positions. You are correct that $1$ and $2$ are $P$ positions, because whoever receives one cannot move and loses. $3$ is then an $N$ position because it can move to $2$. $4$ is $P$ because it can move to $3$ and win. $5,6,7$ are all $N$ because they can move to $4$.
The pattern so far might make you think of powers of $2$. Note that the $P$ positions so far are the powers of $2$. We claim that continues, that powers of $2$ are $P$ positions and all other numbers are $N$ positions.
To prove this, note that from $2^n$ you can only take $\lfloor \frac {2^n-1}2 \rfloor=2^{n-1}-1$ so you cannot get to a smaller power of $2$. If you are at $2^n+k$ with $1 \le k \le 2^n-1$ you can take $k$ and get to $2^n$