yaworsw/euler-manager

---
:id: 306
:name: Paper-strip Game
:url: https://projecteuler.net/problem=306
:content: "The following game is a classic example of Combinatorial Game Theory:\n\nTwo
  players start with a strip of <var>n</var> white squares and they take alternate
  turns.  \nOn each turn, a player picks two contiguous white squares and paints them
  black.  \nThe first player who cannot make a move loses.\n\n- If <var>n</var> =
  1, there are no valid moves, so the first player loses automatically.\n- If <var>n</var>
  = 2, there is only one valid move, after which the second player loses.\n- If <var>n</var>
  = 3, there are two valid moves, but both leave a situation where the second player
  loses.\n- If <var>n</var> = 4, there are three valid moves for the first player;
  she can win the game by painting the two middle squares.\n- If <var>n</var> = 5,
  there are four valid moves for the first player (shown below in red); but no matter
  what she does, the second player (blue) wins.\n\n ![p306_pstrip.gif]({{ images_dir
  }}/p306_pstrip.gif)\n\nSo, for 1 ≤ <var>n</var> ≤ 5, there are 3 values of <var>n</var>
  for which the first player can force a win.  \nSimilarly, for 1 ≤ <var>n</var> ≤
  50, there are 40 values of <var>n</var> for which the first player can force a win.\n\nFor
  1 ≤ <var>n</var> ≤ 1 000 000, how many values of <var>n</var> are there for which
  the first player can force a win?\n\n"