2
$\begingroup$

The problem is:

Two players take turns removing coins from a pile. There are initially $n$ coins, and on each turn, a player can remove $a_1, a_2, \dotsc, a_k$ coins. The player who cannot remove a coin loses.

To solve it, we can use a recurrence: $$w_n = 1 - w_{n-a_1}w_{n-a_2}\dotsm w_{n-a_k}$$ where $w_n = 1$ if the first player has a winning strategy, and $0$ otherwise. The initial cases can be worked out by hand (or by setting $w_m = 1\ \forall m < 0$ and using the recurrence).

For simple cases like choosing $1, 2, 3, 4$ coins every turn, I could work out the pattern by hand. For an arbitrary case like choosing $3, 7, 8$ coins every turn, I could write a computer program to figure out the pattern.

In every case, there appears to be a pattern; how can I prove this? And how can I figure out the said pattern? Thanks for your attention!

$\endgroup$
4
  • 2
    $\begingroup$ What is a pattern? It's clear that the sequence is eventually repeating since the recurrence only depend on the previous m values, and there are only 2^m combinations $\endgroup$
    – Per Alexandersson
    Jun 18, 2015 at 15:51
  • $\begingroup$ For example, if the player can choose 1, 2, 3, or 4 coins every turn, then $w_n$ goes 0,1,1,1,1,0,1,1,1,1,... where 1 signifies a winning strategy for the first player. $\endgroup$
    – shardulc
    Jun 19, 2015 at 1:32
  • 1
    $\begingroup$ In the simple case where the choices are $1,2,3,...,k$ the first player can ensure a win if and only if $n \not\equiv 0\ (\mod k+1 )$, as he can always reduce the number of coins to a multiple of $k+1$, and eventually to zero. $\endgroup$
    – Marconius
    Jul 5, 2015 at 16:16
  • $\begingroup$ @Marconius yes, that is one observation I have already made. Similar results can be obtained for choices $k, k+1, k+2, \dotsl, \ell$. $\endgroup$
    – shardulc
    Jul 5, 2015 at 16:42

1 Answer 1

Reset to default
1
$\begingroup$

These games are called "finite subtraction games" or "substraction games with a finite subtraction set". As Per Alexandersson mentioned, there are only $2^{a_k}$ sequences of 0s and 1s of a length that could affect the next $w_n$, so the sequence of 0s and 1s must be eventually periodic.

There is actually a lot more that you can say. If you have heard of the Sprague-Grundy theorem, the Grundy values of these games are eventually periodic for the same reason. The patterns for a subtraction set of size 2 are well understood, but I think there's a lot we don't know about the periods for substraction sets of size 3.

CGsuite can be used to calculate the Grundy values easily. For instance, in your example of $\{3,7,8\}$, the values start 0,0,0,1,1,1,0,2,2,1,3 and then repeat 0,0,2,1,1, 0,0,2,1,1, … forever. This corresponds to a sequence of your $w$s of 0,0,0,1,1,1,0,1,1,1,1 and then 0,0,1,1,1, 0,0,1,1,1, …

$\endgroup$
2
  • $\begingroup$ Could you elaborate a little on how Grundy values are related to which player wins? This is the first time I'm hearing of the Sprague-Grundy Theorem, and though I technically understood the Wikipedia page, I haven't really gotten a hang of what it intuitively means. $\endgroup$
    – shardulc
    Nov 27, 2015 at 12:58
  • 2
    $\begingroup$ @shardulc Briefly: S-G says every position in a game like this is essentially a single heap of Nim in disguise. A heap of size 0 is a losing position since there is no move available. A heap of any bigger size is a winning position since a good move is "take the whole heap". I don't think the Wiki page for S-G is so great; if you want to learn more, you can read these MIT class notes, or some blog posts I made, or google around. $\endgroup$
    – Mark S.
    Nov 27, 2015 at 16:37

You must log in to answer this question.

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