# Matchstick Game

• Consider the following $$2$$ player finite extensive game. Player $$1$$ moves first. She must choose an integer from $$1$$ to $$10$$, and place that number of matchsticks on the table. Next, Player $$2$$ must add to this by picking an integer from $$1$$ to $$10$$, and adding that number of matchsticks to the ones placed by Player $$2$$. This game goes on until the player places matchsticks such that the total number reaches $$30$$, hence winning the game.
• Describe what choices Player $$1$$ must make to win this game, what number must she start with; then given the choice of Player $$2$$, what number must she pick and so forth.

For the above question, I found that playing $$8$$ in the first round would ensure that Player $$1$$ wins the game, given he plays rationally. I used the logic of backward induction, very vaguely though. In the last stage, for Player $$1$$ to win, he must ensure that the sum of matchsticks on the table is greater than or equal to $$20$$, thus ensuring that Player $$1$$ can choose a number between $$1$$ to $$10$$ such that sum becomes $$30$$ and he wins. For this, it must be the case that in the second last stage of the game, player $$2$$ chooses a number which can never be less than $$19$$, so that the only available options for him would be to make the sum greater than or equal to $$20$$, but not more than $$29$$. In the previous stage to the above Player $$2$$ move stage, Player $$1$$ must ensure that he makes the sum $$19$$. Thus moving backwards, I came to the conclusion that playing $$8$$ guarantees a win for Player $$1$$. If Player $$1$$ plays $$8$$ in the first round, Player $$2$$ can only make the sum greater than $$8$$ and less than $$19$$, such that in next stage, Player $$1$$ can choose such a number so as to make the sum $$19$$. Now Player $$2$$ can choose any number and lose since the sum will never be greater than $$29$$.

This is the only winning strategy I could find for Player $$1$$. I am not sure if this is correct or whether there are more winning strategies. Please help me in finding the complete winning strategy for Player $$1$$. Also, how do we formally write down the strategy (winning) set? $$8$$, $$11-s_j^1$$, $$11-s_j^2$$ is the only way I could think of writing the strategy set. Please correct me. Thanks a lot!

## 2 Answers

You've established that a player getting to 8 or 19 seals a win. You want to understand whether player 1 has any options other than starting with 8, to win.

Consider it from player 2's perspective. What is player 2's best strategy if player 1 picks a number less than 8? What is player 2's best strategy if player 1 picks 9 or 10?

The answer to both, is contained in the first sentence I wrote above.

• Each player would want to reach either 8 or 19 to seal a win, given the other player's strategies. If player 1 does not play 8, player 2's best response would be to choose a number so as to make the sum 8 or 19. Is this correct? – S.Rana Feb 20 '19 at 20:56
• @ShinjiniRana exactly! So if player 1 picks anything other than 8, it's a losing strategy. – 410 gone Feb 20 '19 at 21:02

The backtracking method you used is a good one. Now that you found a solution, it is nice to discover some patterns and generalizations.

We could generalize this game to reaching any goal G with any choice of integer from n to N. You can find that the winning strategy is making sure that you reach any number G-(n+N)*i, where i is an integer. These are all the winning spots. The lowest winning spot can be found by G modulus (n+N)

Mathematical games are fun, aren't they?

• Thank you for the general solution. What method did you use to derive such a solution? Also, I can't seem to understand the step you used to find the lowest winning spot, G modulus (n+N). Could you please elaborate? And yes, mathematical games are really fun. – S.Rana Feb 21 '19 at 13:57
• I just tried a couple of combinations, discovered a reoccurring pattern and tried to understand the pattern. About the modulus operation: that is just subtracting (n+N) from G until the remainder is less than (n+N) You can check the Wikipedia on modulus. en.wikipedia.org/wiki/Modular_arithmetic – jos Feb 25 '19 at 11:16
• Oh okay! You seem to have missed the minus sign in the expression G - modulus(n+N). This matches the solution. Thank you! – S.Rana Feb 25 '19 at 12:25
• No, you misunderstood me. with G modulus(n+N) I mean the remainder after doing the division G/(n+N). 30/11 = 2, remainder 8. 8 is the lowest winning spot. – jos Feb 28 '19 at 12:52
• Sorry for the confusion, Jos. I checked the link you sent after replying to you and seem to have forgotten to delete the comment. I understood it from the Wikipedia Page. Thank You for the reply. – S.Rana Feb 28 '19 at 14:36