2
$\begingroup$
  • 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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – S.Rana Feb 20 at 20:56
  • $\begingroup$ @ShinjiniRana exactly! So if player 1 picks anything other than 8, it's a losing strategy. $\endgroup$ – EnergyNumbers Feb 20 at 21:02
0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – S.Rana Feb 21 at 13:57
  • $\begingroup$ 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 $\endgroup$ – jos Feb 25 at 11:16
  • $\begingroup$ Oh okay! You seem to have missed the minus sign in the expression G - modulus(n+N). This matches the solution. Thank you! $\endgroup$ – S.Rana Feb 25 at 12:25
  • $\begingroup$ 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. $\endgroup$ – jos Feb 28 at 12:52
  • $\begingroup$ 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. $\endgroup$ – S.Rana Feb 28 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.