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

<p>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) </p>

<p>Mathematical games are fun, aren't they?</p>

CC BY-SA 4.0
2019-02-21T13:57:02.820Z
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
CC BY-SA 4.0
2019-02-25T11:16:42.517Z
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. https://en.wikipedia.org/wiki/Modular_arithmetic
jos
CC BY-SA 4.0
2019-02-25T12:25:14.217Z
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
CC BY-SA 4.0
2019-02-28T12:52:22.513Z
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
CC BY-SA 4.0
2019-02-28T14:36:21.510Z
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
CC BY-SA 4.0
2019-02-21T08:44:58.007Z
2019-02-21T08:44:58.007Z
jos
<p>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.</p>

<p>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?</p>

<p>The answer to both, is contained in the first sentence I wrote above.</p>

CC BY-SA 4.0
2019-02-20T20:56:29.150Z
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
CC BY-SA 4.0
2019-02-20T21:02:37.633Z
@ShinjiniRana exactly! So if player 1 picks anything other than 8, it's a losing strategy.
410 gone
CC BY-SA 4.0
2019-02-20T20:50:36.633Z
2019-02-20T20:50:36.633Z
410 gone
<ul>
<li>Consider the following <span class="math-container">$2$</span> player finite extensive game. Player <span class="math-container">$1$</span> moves first. She must choose an integer from <span class="math-container">$1$</span> to <span class="math-container">$10$</span>, and place that number of matchsticks on the table. Next, Player <span class="math-container">$2$</span> must add to this by picking an integer from <span class="math-container">$1$</span> to <span class="math-container">$10$</span>, and adding that number of matchsticks to the ones placed by Player <span class="math-container">$2$</span>. This game goes on until the player places matchsticks such that the total number reaches <span class="math-container">$30$</span>, hence winning the game.</li>
<li>Describe what choices Player <span class="math-container">$1$</span> must make to win this game, what number must she start with; then given the choice of Player <span class="math-container">$2$</span>, what number must she pick and so forth. </li>
</ul>

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

<p>This is the only winning strategy I could find for Player <span class="math-container">$1$</span>. 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 <span class="math-container">$1$</span>. Also, how do we  formally write down the strategy (winning) set? <span class="math-container">$8$</span>, <span class="math-container">$11-s_j^1$</span>, <span class="math-container">$11-s_j^2$</span> is the only way I could think of writing the strategy set. Please correct me. Thanks a lot!</p>

<microeconomics><game-theory><self-study><extensive-games>
Matchstick Game
S.Rana
# Matchstick Game

(Asked by: username_0 on 2019-02-20)

* 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!

**Tags:** microeconomics, game-theory, self-study, extensive-games

---

## 2 answers

### Answer by username_2 on 2019-02-20. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: @ShinjiniRana exactly! So if player 1 picks anything other than 8, it's a losing strategy.  

---

### Answer by username_1 on 2019-02-21. Score: 0

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?

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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. https://en.wikipedia.org/wiki/Modular_arithmetic  
> **username_0**: Oh okay! You seem to have missed the minus sign in the expression G - modulus(n+N). This matches the solution. Thank you!  
> **username_1**: 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.  
> **username_0**: 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.  

---

