Jump to content

Puzzles/Two-player games/Picking game/Solution

From Wikibooks, open books for an open world

The puzzle as stated doesn't quite state how a "tie" is possible, unless you can refuse to draw. If we assume you -must- draw 1 or 2 matches on your turn, then:

  • 1 match left - Draw 1 and win (winning state)
  • 2 matches left - Draw 2 and win (winning state)
  • 3 matches left - Drawing 1 or 2 matches puts your opponent in such a state that (s)he will win (losing state)
  • 4 matches left - Drawing 1 puts your opponent into state 3, where no matter what (s)he draws (s)he loses (winning state)
  • 5 matches left - Drawing 2 puts your opponent into state 3, where no matter what (s)he draws (s)he loses (winning state)
  • 6 matches left - Drawing 1 or 2 matches puts your opponent in a winning state (losing state)
  • 7 matches left - Drawing 1 puts your opponent into state 3, where no matter what (s)he draws (s)he loses (winning state)
  • 8 matches left - Drawing 2 puts your opponent into state 3, where no matter what (s)he draws (s)he loses (winning state)
  • 9 matches left - Drawing 1 or 2 matches puts your opponent in a winning state (losing state)


Basically, if there are 3n matches, you're in a losing state, because no matter what you choose, your opponent can leave you in a state 3(n-1) by choosing the opposite (IE 1 + 2 == 3 or 2 + 1 == 3). When n = 1, this 3(n-1) = 3(0) = 0 and your opponent wins because (s)he has drawn the last match. If there are 3n+1 or 3n+2 matches, you choose 1 or 2 respectively, and always leave your opponent 3m matches and you will win, and by the same logic you will win.

So basically, if you both play perfectly, the first player can only win if n Matches mod 3 is nonzero.

Alternatively, if you can refuse to draw a match (possibly intended by the question) you would always draw n mod 3 matches - if it's a multiple of 3 you refuse to draw, otherwise you draw leave a multiple of 3 matches.