Pile of gold coins

Logic Level 3

You play a game with a pile of $N$ gold coins.

You and a friend take turns removing 1, 3, or 6 coins from the pile.
The winner is the one who takes the last coin.

For the person that goes first, how many winning strategies are there for $N < 1000?$

Clarification: For $1 \leq N \leq 999$ , for how many values of $N$ can the first player develop a winning strategy?

The answer is 666.

2 solutions

Mark Hennings
Jun 3, 2016

The Sprague-Grundy function for this game is the function $G\,:\, \mathbb{N} \to \mathbb{N} \cup \{0\}$ , where $G(1) = 1\;,\; G(2) = 0 \;,\; G(3) \;= \; 1\;,\; G(4) = 0 \;,\; G(5) = 1 \;,\; G(6) \; = \; 1$ and $G(n) \; =\; \mathrm{mex}\{G(n-1),G(n-3),G(n-6)\} \qquad \qquad n \ge 7$ where $\mathrm{mex}$ means "minimum excluded", so that the $\mathrm{mex}$ of a set is the least nonnegative integer not in that set.

Losing piles (for the next player to play) are ones with $n$ coins, where $G(n) = 0$ . Piles with $n$ coins with $G(n) > 0$ are ones for which the first player has a winning strategy. Since $G(n) > 0$ , $0$ must belong to the set $\{G(n-1),G(n-3),G(n-6)\}$ , and so the first player must have a move which presents the second player with a pile with $m$ coins, with Grundy number $G(m) = 0$ . This means that $0$ does not belong to the set $\{G(m-1),G(m-3),G(m-6)\}$ , which means that any move that the second player makes presents the first player with a pile of coins with positive Grundy number again. Note that it is only possible to finish the game from a pile of coins with $1$ , $3$ or $6$ coins in it (and the Grundy number of each of these pile sizes is $1$ ).

Thus we see that the first player must win precisely when she starts with a pile of coins with positive Grundy number.

With this recursive definition for $G$ , it is easy to prove that the pattern of wins and losses pointed out by Geoff is true.

There are $\boxed{666}$ numbers between $1$ and $999$ which have positive Grundy numbers.

This is a great write up, Mark... Thanks for posting!

Geoff Pilling - 5 years ago

Geoff Pilling
Jun 2, 2016

Let $f(N)$ represent whether you can win or not on the first moven given that you start out with N coins. You can quickly see that for $1\leq N\leq9$ , $f(N) = W,L,W,L,W,W,W,W,L$ . This pattern repeats for $N>9$ . So, $2/3$ of the strategies will win, since $2/3$ of these are winning positions for the person going first, $999$ values of $N$ will be a winning strategy. So, $N=\boxed{666}$

This description is far from complete, please see @Mark Hennings solution below for a more complete explanation.

Hmmmm , I still have some doubts concerning this calculation. I was tempted to do the same and arrive at that answer but if you check attentively it may be wrong or I don't know where I mistake.

The pattern doesn't repeat in any 10 numbers that way in my opinion as a result of the fact that the expressed way regarding of loses and wins in 10 numbers varies. Just to make things clear , name a losing number the number of coins for which a player will lose under optimal play from both players. Yes , the first losing numbers will be 2 , 4 , 9 and starting from them all losing numbers further can anyway be generated because if a player can make the other arrive at a losing number then it can also be said that he/she has winning strategy and a player can arrive at a losing number just by the restrictions of the number of coins he can take from the pile , that being 1 , 3 and 6. To obtain anyway the rest of the losing numbers observe that if a player can't arrive at a losing number by taking a number of coins he has losing strategy and therefore all numbers which can't be derived by adding to at least one losing number 1 , 3 or 6 are losing numbers.

To calculate all the losing numbers , or list them or whatever , maybe it's better to start with 9 to show directly what I mean. For starting with 9 it's clear that 9+2 = 11 is a losing number because there is no possible way to generate it from it and also from any other losing number since the other loosing numbers are at a distance bigger than 6 and also that 11+2 = 13 is a loosing number therefore that 9 , 11 , 13 are continuous losing numbers by the rate +2. The numbers that can be generated further by this same rate , +2 , aren't losing numbers and also all the other numbers until the maximum that can be obtained from them 13+6 = 19 aren't losing numbers the next loosing number that can be observed being 20. This is therefore would be the iterative expression for generating all loosing numbers.

That is there will be 3 loosing numbers ( a0 ,a1 , a2) from 2 on 2 while all the other between the losing number a0 and a2+6 can be generated. In such a repeating sequence there are between the numbers a0 and a2 including them 5 numbers and from a2 to a2+6 6 numbers. That meaning therefore that 11 numbers for any interval of loosing numbers are there. Starting from 9 and including this number in an interval calculating the number of all loosing numbers is simple to do. Because anyway it is being started with 9 the calculation of all loosing numbers until some number should anyway be done from the number 8 and would have the form of 8 + 11 * k that meaning that by starting from the number 8 there will k intervals of 11 numbers until some number. Considering that 999 = 8 + 11* 90 + 1 this meaning that there are 90 intervals of 11 numbers and one 1 number of some other interval starting with 8 there would be 90*3+1 losing numbers (3 in any interval) therefore leading by adding the 2 from the 8 numbers before to 273. Then there are 726 winning strategies.

Anyway , I don't know where I am wrong so I'd like to be corrected and sorry for the rushed writing of this but it's clear to me that you'll understand.

I wanted to do the same way as you after I saw that the answer introduced by me is wrong yet calculating things like that I arrived at the conclusion that it may be right.

A A - 5 years ago

I do not really follow your argument, but you are wrong in saying that the next losing number after $13$ is $20$ , since $18$ is also a losing number.

if Player 1 plays $1$ , Player 2 plays $6$ , which means that Player 1 now faces the losing number $11$ .
if Player 1 plays $3$ , Player 2 plays $6$ , which means that Player 1 now faces the losing number $9$ .
if Player 1 plays $6$ . Player 2 can play either $1$ or $3$ , which means that Player 1 now faces one of the losing numbers $11$ or $9$

Mark Hennings - 5 years ago

You followed it actually because you understood where I was wrong. That's exactly where anyway indeed I observed am wrong and Geoff helped , and thanks for explaining.

To clarify again and to assure you understood my argument I tell that you can generate all loosing numbers by the other loosing numbers. Starting from 9 because it is more appropriate for an argument like this there are the loosing numbers 9 , 11 , 13. They will generate all the winning numbers until the number 17 indeed. This actually is meant generally for any 3 consecutive from two in 2 loosing numbers in an interval of 9 because any 3 loosing numbers. That means that given 3 loosing numbers they have the form a , a+2 , a+4 and generate all winning numbers until a+8. This meaning that after a+8 will be again another interval of three loosing numbers and so on up to some point meaning that because of the repetitive structure all intervals of 9 numbers and therefore all the numbers including the loosing numbers and the winning numbers anyway generated from this numbers will have 3 loosing numbers , thing which can be considered anyway synthetic anyway.

A A - 5 years ago

Did you see @Mark Hennings write up below? Its likely more convincing than mine! :)

Geoff Pilling - 5 years ago

Not completely but I still have doubts cause what I wrote still is pretty convincing too anyway or anyways so I think , and btw cute problem.

But of course I will look a little later at that also but still I have doubts regarding it anyway since that calculation done by me it's straightforward and I don't spot my error so help me please understand.

A A - 5 years ago

@A A – Looking in this thread, A A, It seems like you sometimes use flawed reasoning to find the solution. You make some assumptions in your initial "proof" without justifying them. For example, you notice the difference of +2 between some losing numbers, then you only consider numbers with that difference (i.e. the odds). You provide no justification for this. It "makes sense to you" because you see a pattern and assume it works, but you must prove rigorously that it works. This is a large source of error for many: when solving problems, you must be careful not to make unreasonable assumptions.

You attempted a proof by saying that winning positions are positions that can be created by adding one of {1, 3, 6}. But you make an extra step in saying that "you can generate all losing numbers by adding a common difference to the previous losing number."

Please try to lay out your argument more clearly, and avoid using words such as "whatever" or "anyways." And make sure to provide justification for your explanations. When solving the problems, make sure you know that every step you are taking is justified.

Jacob Swenberg - 5 years ago

@Jacob Swenberg – Well , I do agree with you about the rigor point and especially about the articulated idea that whenever you try to really prove something you need to assure every step is justified and right. Without that any kind of reasoning is more of a speculation ( which is itself very important and in my opinion necessary always too) as it doesn't provide a solid and complete understanding which nonetheless is the very purpose of what anyone who tries to solve this type of problem tries to achieve when solving them and anyway I really liked that I see someone who thinks like me and expresses that as good as you were able to do it and besides that I really appreciate the fact that you tried to help by providing a very good and justified point so thanks for those remarks.

Anyway what I have written there was more of a general illustration and that's why I skipped explaining in too much detail some stuff like the +2 thing. It was intended to just sketch the reasoning but I see how it may appear that the reasoning can be flawed since I am not rigorous because I don't explain every step (whenever it is more complicated and demands pretty much explanation) so I'll try to do that explanation now clearly.

Assuming there is a winning strategy (because it is not certain at this point of the proof that such a strategy is firstly) and that the game is regulated by perfect or optimal play from both players it has to be assumed that there are some positions for which if a player has loses and some by which a player wins therefore name the corresponding numbers of those losing and winning positions losing and wining numbers where a losing number is a number of coins by which if a player receives he is certain that he loses , a winning number being defined by analogy anyway. Observe that the strategy for winning the game would imply , for some sequence of losing and winning numbers which has to be determined as things are considered right now just by their form that a player should make his opponent arrive at a losing number therefore meaning that if it is possible for a player to give the other player a losing number the winning player has a winning strategy thing which is possible just when by the allowed set of moves described by the game that winning player can arrive from it's number of coins at a losing number.

Therefore the winning numbers provide a winning strategy as long as the winning player is assured by having such a number of coins at his move that he can make the other player lose but anyway this excepting the winning numbers 1, 3 and 6 which provide a winning strategy without involving the second player and therefore without implying that the he must arrive at a losing number. Because a number is a winning number just if it can reach by the allowed moves a loosing number all loosing numbers can be used to determined those numbers that can reach them and further they can also be used to determine which numbers can't reach them therefore determining and being capable of generating the other winning and losing numbers.

Therefore in order to understand which are the loosing and winning numbers corresponding to some allowed moves and a number of coins in the initial pile it should be understood and therefore obtained a general description of the way by which the loosing numbers generate the other winning and loosing numbers considered from the sequence of the possible number of coins. That meaning a general description of the generation of the winning and loosing numbers dependent on loosing numbers because if such a description is obtained , describing abstractly how the loosing numbers determine the winning and loosing positions the problem is solved.

The procedure to determine the winning numbers based on loosing numbers would be that of adding to the loosing numbers the number of allowed moves because by this it means that the number obtained from adding to the loosing number a number of allowed coins by one move can arrive in the moment of the game at the loosing number and therefore make the other player loose.

For the case of the problem , starting from 1 , 3 and 6 the first loosing numbers will be 2 and 4 and because by adding to 2 or 4 one of the numbers that represent an allowed move namely anyway 1 , 3 or 6 it can be checked that all numbers until 9 can be obtained where 9 is a loosing number as all numbers that can reach 9 by adding 1 , 3 or 6 are winning numbers. Anyway this reasoning applies also for 9+4=13 which is a loosing number. Therefore starting from number 9 there are generated the loosing numbers 11 and 13. Because these numbers are of the form a , a+2 , a+4 calculating or determining their behavior by addition with 1 , 3 , 6 is easy giving that for numbers of this form the number which can't be generated by them , and therefore the loosing number after them will be at a distance of a+9. Since this of course repeat as the number of allowed moves doesn't vary and therefore can be expressed in a regular way the next loosing numbers are also of the form a , a+2 , a+4 and behave in the same way (or generate in the same way) the winning and loosing numbers until a+9 meaning that in every such sequence there are 9 numbers until the last. Anyway observe that every sequence of 3 consecutive loosing numbers generates numbers just until a+10 but even if the range is greater and exceeds the next loosing number than generates another sequence of 3 consecutive numbers this doesn't affect neither the recursive nor anyway the regularity of repetition observed as it was already implied in elaborating it. Considering therefore further for any 9 numbers starting with 9 inclusive (or with 8 but not inclusive) anyway there are because every 3 consecutive loosing number generate 9 contain 9 numbers from which just 3 are loosing numbers the other being winning the total numbers can be calculated pretty easily and gives finally the result.

Emmmm, yea. It's not completely clear but I tried at least anyway.

A A - 5 years ago

So where do you think the values for 10-18 differ from those from 1-9?

Geoff Pilling - 5 years ago

Yep , you are right. They don't and I wasn't attentive and thanks anyway.

A A - 5 years ago

@A A – No problem... Glad I could help! :)

Geoff Pilling - 5 years ago

It looks like your assumption is that the sequence repeats itself for every 11 values of N. However, my claim is that the frequency repeats itself for every 9 values, therefore making a bit easier to solve since 999 divides evenly by 9.

If you look at the number 15, which is a win, (since you can remove 6 coins and leave him with 9 which we both agree is a losing situation for the player presented with 9) you will see that this is more consistent with the pattern repeating itself every 9 coins added. i.e $f(N) = f(N-9)$ for $N>9$ .

Does that make sense?

Geoff Pilling - 5 years ago

It does make almost complete sense , especially now , that I have seen where I have mistaken in calculation anyway.

In order to make things clear , the idea in what I wrote there is that you can generate all loosing and winning numbers provided that the players play optimally from the previous loosing numbers. It leads to the pattern you have mentioned and is made in every sequence of 10 numbers of 3 loosing numbers and I've done a mistake in calculation because the interval which has 3 "consecutive" loosing numbers contains just 9 elements not 11 since not all numbers until the last loosing number + 6 can be obtained as I initially thought.

For example if you want to generate all loosing numbers until 20 apart from 2 and 4 you can start with numbers 9 , 11 , 13 where all winning numbers are those by which you can reach one of the loosing numbers with the allowed moves and all loosing numbers are those which can't reach those. By this all loosing numbers can be generated and calculated in a synthetic way obtaining because the loosing numbers are of the form a , a+2 , a+4 ( increasing at a constant rate) that by addition with the same number of coins permitted to be taken at a move (1 , 3 , 6) for each of them you can obtain for that sequence of 3 loosing numbers all numbers until a+8.

That meaning for the case of loosing numbers being 9 , 11 , 13 all the numbers until 9+8=17 and implying the next interval opens with 18 which is a loosing number anyway.

As there would be a of 3 consecutive loosing numbers every 9 numbers then you will have something like 8 + 9 * k + 1 = 999 or 9 + 9*k = 999. That means that from 8 there are a number therefore of k intervals of 9 numbers which contain 3 loosing numbers. Or in other words anyway there will be a number therefore of 111 intervals of 9 numbers that contain 3 loosing numbers. By considering things like that it is clear that there must be this numbers.

Thanks , you are very kind to look at what I wrote and explain me. I'm a little bit sorry for requesting this as it became pretty clear after I left where I went wrong. Nonetheless this can in some way be an interesting clarification of the fact that you are right. I think it is a clarification because it points out exactly , articulately meaning by that , what makes those intervals anyway.

A A - 5 years ago

Pile of gold coins

The answer is 666.

2 solutions

0 pending reports