3
$\begingroup$

Please help me with following problem.

There are 100 stones. Two persons play the following game: the first person takes 1 stone. The second takes one or two. Then the first person takes one or two or three and they continue in this way. The winner is the person who takes the last stone. Who has the winning strategy and what strategy he applies to win the game?

I verified the first smaller values for the number of stones, and deduced that the first person wins the game if the number of stones is 1, 4, 5, 9, 10, ... while this sequence for the second person is 2, 3, 6, 7, 8, ... .

I guess there may be a connection between the above sequnces with the triangular numbers but I can not explain the problem in a general case. Thank you.

$\endgroup$
5
  • $\begingroup$ You could do a somewhat tedious backwards induction on the states $(S, n)$ where that notation means that you have $S$ stones and you are starting with $n$ choices, Here, you are starting with $(S, n)=(100,1)$. Noting that $(S,n)$ is a guaranteed win for player $1$ if $n≥|S|$, there are only finitely many states to worry about. Perhaps there is a cleaner way, however. $\endgroup$
    – lulu
    Apr 2 at 19:15
  • $\begingroup$ To be clear, the number of stones a player is permitted to take increases by $1$ at each turn? $\endgroup$ Apr 2 at 19:31
  • $\begingroup$ @RobertShore Yes, the number of choices increases by 1 at each turn. $\endgroup$
    – Fermat
    Apr 2 at 19:37
  • $\begingroup$ @lulu Thanks, following your notation, one case (which is clear of course) is if n<s<=n+2, the player whose turn it is (i.e., with n choices) loses the game. $\endgroup$
    – Fermat
    Apr 2 at 19:58
  • $\begingroup$ Right. If you automate the process, it should run quickly. Of course, this method wouldn't work well for $10^9$ stones. $\endgroup$
    – lulu
    Apr 2 at 20:05

2 Answers 2

3
$\begingroup$

For any integer $s\ge 1$, the numbers in the interval $[s^2,s(s+1)-1]$ are winning for the first player, while the numbers in the interval $[s(s+1),(s+1)^2-1]$ are losing for the first player.

Let me show how to win whenever the initial number of stones is a perfect square, $s^2$. Recall that $$ s^2=1+3+5+\dots+(2s-1) $$ Call the players Alice and Bob, with Alice going first.

  • During the first turn, Alice removes $1$ stone.

  • During turns two and three, Alice will ensure that the combined number of stones removed between Alice and Bob removed is $3$. That is, if Bob removes $1$ stone on turn two, then Alice removes $2$ stones on turn three. If Bob instead removes $2$ stones on turn two, the Alice removes $1$ stone on turn three.

  • During turns four and five, Alice will ensure that the combined number of stones removed is $5$. If Bob removes $b$ stones on turn four, then Alice removes $5-b$ stones on turn five.

The pattern continues. During each pair of consecutive turns numbered $2t$ and $2t+1$, where $t\ge 1$, Alice ensures that a combined total of $2t+1$ stones are removed. Since we keep removing consecutive odd numbers from the pile, we will eventually remove $1+3+\dots+(2s-1)=s^2$ stones after Alice's turn. This empties the pile and secures the win for Alice.

If instead the number of stones is of the form $s(s+1)$ for some $s$, then we use the fact that $$ s(s+1)=2+4+6+\dots+2s $$ to give a similar strategy for Bob. For each $t\in \{1,\dots,s\}$, during turns numbered $2t-1$ and $2t$, Bob will ensure that the combined number of stones removed is $2t$.

There is one last part of this problem I am leaving for you to figure out; what is the winning strategy for numbers not of the form $s^2$ or $s(s+1)$? Previously, we showed that between turns numbered $t$ and $t+1$, that one of the players can ensure that the total number of stones removed is $t+1$. You can also show that the same player can force the number of stones removed to be $t+2$. Use this extra freedom to solve the other cases.

$\endgroup$
1
  • $\begingroup$ Thank you very much Mike, this is really an elegant solution to this problem. I will figure out the remainig part of the proof. $\endgroup$
    – Fermat
    Apr 2 at 21:35
1
$\begingroup$

Let us draw a diagram. It is a row of small integers, where a number is red if the first player wins in the game with this starting number of stones, and green if the second player wins:

enter image description here

A pattern can be seen! $1$ green, $1$ red, $2$ green, $2$ red, $3$ green, $3$ red, and so on. Let us explain why this pattern persists for greater numbers. I won’t present a rigorous proof, just an idea, illustrated by particular examples.

How can the first player win, if the game starts at the beginning of the red group? Let’s say, at $9$ stones. What groups of numbers are before $9$? There are $$1+1+2+2+3$$

positions. Combine these numbers as follows:

$$(1)+(1+2)+(2+3).$$

The first player easily wins, just taking stones so that the group in brackets is taken whole. After his first move $1$ stone is taken, after his second move $(1)+(1+2)$ stones are taken, after his third move $(1)+(1+2)+(2+3)$ stones are taken. He always wins this way.

What if the game starts not in $9$ but in the same red group? Then there are $$1+1+2+2+3+k$$

positions before the starting number, where $k$ is less then the number of positions in the red group (equal to $3$ in this case, it is also the sequential number of the red group). Combine these numbers as follows:

$$(1)+(1+2[+1])+(2+3[+1]).$$

Where did $k$ go? It dispersed into $+1$s. $k$ is small enough for that. So now the first player just makes his move $1$ stone longer a needed number of times. Note that these moves are allowable by the game rules.

The same with the green groups. If the game starts at the leftmost green number of the group (say $12$), then there are

$$1+1+2+2+3+3$$ positions before. Combine them as $$(1+1)+(2+2)+(3+3).$$ The second players wins by “completing the bracket”. $1+1$ stones after his first move, $(1+1)+(2+2)$ after his second move, $(1+1)+(2+2)+(3+3)$ after his third move, and so on.

If the game starts somewhere in the green group, then there are $$1+1+2+2+3+3+k$$ positions before, where $k$ is less than the sequential number of the green group. So the positions can be combined like this: $$(1+1[+1])+(2+2[+1])+(3+3[+1]).$$

Again, $k$ is small enough, and the moves of the second player are allowable. So the second player wins.

Note 1. To draw an analogy with the @MikeEarnest ‘s answer, note that a beginning of a red group is a sum of consecutive odd numbers, hence is a square. The beginning of a green group is “halfway” between squares, and is a number of the from $s(s+1)$.

Note 2. Number $100$ is the beginning of the red group, so the first player wins.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .