The question is: There are 219 matches on a table and 2 players , each player can take 1,3 or 4 matches off the table , winner is who takes the last match. is there a winning strategy that guarantees for the second player to always win? .

I can't think of a way to calculate without having to do the recursion myself , now maybe 219 matches isn't that bad but if it was 1000 matches that wouldn't be so efficient.

I'd appreciate the help


1 Answer 1


When the number of matches is of the form 7$k$ or 7$k$ + 2, the second player wins; otherwise, the first player wins. I cannot claim to have an intuition of why this should be so, but once you write the program and notice the pattern, it is easy to prove by induction.

#include <stdio.h>

#define MAX_N 100

bool w[MAX_N]; /* true = player 1 wins; false = player 2 wins */

int main() {
  w[1] = true;
  w[2] = false;
  w[3] = true;
  w[4] = true;

  for (int i = 5; i < MAX_N; i++) {
    w[i] = !w[i - 1] || !w[i - 3] || !w[i - 4];
    if (!w[i]) {
      printf("Player 2 wins for n=%d\n", i);

The program basically hard-codes the trivial cases, then says "Player 1 wins if and only if there exists a move that takes the game into a state where Player 2 wins". Output:

Player 2 wins for n=7
Player 2 wins for n=9
Player 2 wins for n=14
Player 2 wins for n=16
Player 2 wins for n=21
Player 2 wins for n=23
Player 2 wins for n=28
Player 2 wins for n=30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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