Dynamic programming , Matches game and winning strategies

Question

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

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
...