Don't be Greedier

Question

Consider the following two-player game, Don't be Greedier, that involves players taking alternate turns removing pebbles from one pile of pebbles, subject to the following rules:

(1) The player to remove the last pebble or pebbles from the pile wins the game.

(2) On the very first move of the game, the player to play is not allowed to remove all the pebbles and win immediately (that would be greedy).

(3) After the first move, the number of pebbles removed can't be more than the number of pebbles removed in the turn immediately prior (that would be greedier). That is, the sequence of numbers of pebbles removed on each turn is a monotonically non increasing sequence.

Starting with a pile of 12 pebbles, which player would win a game of Don't be Greedier, assuming optimal play?

Answer 1

You can make a minimax table, starting with 1, should only take a couple minutes. For row $R$ and column $C$, does the player win if there are $R$ pebbles left and he is allowed to draw up to $C$:

$$\begin{array} {c|c|c|c|c|c|} \text{Pebbles \ Draws} & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1 & W \\ \hline 2 & L & W \\ \hline 3 & W & W & W \\ \hline 4 & L & L & L & W \\ \hline \end{array}\\ \vdots \\ \begin{array} {c|c|c|} & ... & 12 \\ \hline 12 & ... & ? \\ \hline \end{array}\\ $$

Answer 2

The first player can win. Here is a winning strategy (someone else may have a more elegant explanation).

Winning Strategy

Say the person who goes first is called $F$, and the person who goes last is called $L$.

If a person removes one pebble from an odd pile, that person wins the corresponding sequence of removing one pebble at a time. This makes it easy to manufacture a winning strategy.

$F$ first removes four pebbles to reduce the stack to eight.

$L$ has two options that do not obviously lose: remove two or remove four pebbles.

If $L$ removes two pebbles, there are six left. $F$ obviously does not want to remove one pebble, because then $L$ can remove one pebble from an odd pile and win. So $F$ and $L$ both remove two pebbles at a time, and we find that $F$ wins.

If $L$ removes four pebbles, there are four pebbles left. $F$ can remove the remaining four and win.

Thus, this strategy wins $F$ the game regardless of the actions of $L$. In other words, the person who chooses first can win.

Proof: this is the only winning strategy for $F$

The strategy above is the strategy of removing four pebbles at the start. Every other part of the strategy is in response to the moves of $L$.

If $F$ removes six or more, $F$ clearly loses.

If $F$ removes an odd number, he loses when $L$ removes one.

If $F$ removes two, the corresponding move sequence of removing two pebbles at a time causes $F$ to lose.

The only other option is for $F$ to remove four pebbles at the start, which is the winning strategy presented above.

Answer 3

The first player can win if he/she removes $4$.

The second player has to remove $4$ or $2$ because if he/she removes $1$ or $3$, the first player will win by removing only $1$s.

However, if the second player removes $4$, the first player will win by removing $4$ again.

On the other hand, if the second player removes $2$, the first player removes $2$. Then, the first player has to remove $2$ again otherwise the first player will win by removing $1$s. However, in this case, the first player will win by removing $2$ again.

Hence, the first player can win in this strategy.

By the way, if the first player removes $n\not=4$, then the second player can win.

If the first player removes an odd number $n$, then the second player will win by removing $1$s only.

If the first player removes $2$, the second player will win by removing $2$s untill the first player removes $1$. If the firt player takes $1$, then the second player removes $1$s only.

If the first player removes an even number $n\ge 6$, then the second player will win by removing $12-n$.

Answer 4

If the 1st player removes n pebbles with $n\geq6$ or $n=1$ then 2nd player wins. Assume that 1st player removes n pebbles with $n\in \{ 2,3,4,5\}$. If $n=3 or 5$ then 2nd player removes one pebbles and thus wins in the end since after the 1st player plays there is an odd number of pebbles remaining. If $n=2$ and 2nd player removes 1 pebble during first round then 1st player wins. If 2nd player removes 2 pebbles during the first round then he wins in the end. If $n=4$ then the 1st player wins and its easy to see all possible cases. In general if a player reaches the point to remove pebbles from an odd number of them he removes one and wins in the end.

Answer 5

One can show that the second player to play wins if and only if the starting number of stones is exactly a power of two.

Proof: Let $(n, k)$ denote the position where $n$ stones remain and $k$ stones are the maximum allowed to be taken. If $k\geq n$ the next player to play wins. Otherwise, we show that the first player wins if and only if $k$ is at least equal to the place value of the least significant $1$ when $n$ is written in binary. (This is $1$ if $n$ is odd, $2$ if $n$ is even and not divisible by $4$, $4$ if $n$ is divisible by $4$ and not $8$, and so on.)

The proof is by induction on $n$. Suppose this is shown for all values smaller than $n$, that $m$ is this place value, and that $k\geq m$. Then, the first player may remove $m$ stones, leaving us in the position $(n-m, m)$. The least significant $1$ of $n-m$ is in a higher place than that of $n$ since the binary expansion of $n-m$ is just that of $n$ with the least significant $1$ removed, so $m$ is less than the place value of the least significant $1$ in $n-m$. By induction the next player to play cannot win, so the player who just moved will win.

On the other hand, suppose that $k<m$. Then no matter how many stones the first player removes, he will introduce a $1$ with a place value less than the number of stones he removes; that is, he moves to $(n-x, x)$ where $x$ is greater than the place value of the least significant $1$ in the binary expansion of $n-x$. By induction the second player will win.

Since the original position of the game is $(n, n-1)$ the second player wins if and only if the least significant $1$ in $n$ has place value at least $n$; that is, if $n$ is a power of two. In particular, if $n=12$ then the first player wins.