Two players play a game on a pile of beans. On each player's turn, they may take exactly , , or beans from the pile. One player goes first, and then the players alternate until somebody wins. A player wins when they take the last bean from the pile. For how many between and (inclusive) does the second player win?
Solution
1. Understanding the Game Dynamics:
- The game involves two players taking turns to remove 1, 4, or 7 beans from a pile.
- The player who takes the last bean wins.
- We need to determine for which values of (the initial number of beans) the second player has a winning strategy.
2. Analyzing Winning and Losing Positions:
- Let's denote a winning position by and a losing position by .
- A position is a losing position if every move from that position leads to a winning position for the opponent.
- Conversely, a position is a winning position if there is at least one move that leads to a losing position for the opponent.
3. Base Cases:
- : Losing position () because the player to move cannot make a move.
- : Winning position () because the player can take the last bean and win.
- : Winning position () because the player can take 1 bean, leaving 1 bean for the opponent, who then loses.
- : Winning position () because the player can take 1 bean, leaving 2 beans for the opponent, who then loses.
- : Winning position () because the player can take 4 beans and win.
- : Winning position () because the player can take 4 beans, leaving 1 bean for the opponent, who then loses.
- : Winning position () because the player can take 4 beans, leaving 2 beans for the opponent, who then loses.
- : Winning position () because the player can take 7 beans and win.
- : Losing position () because any move (taking 1, 4, or 7 beans) leaves a winning position for the opponent.
4. Pattern Recognition:
- From the base cases, we observe that and are losing positions.
- We can generalize this pattern: and are losing positions.
- Extending this pattern, we find that are losing positions.
5. **Counting the Values of Between 2014 and 2050:**
- We need to count the number of integers in the range such that .
6. Finding the Specific Values:
- For :
- The smallest is 2016 (since ).
- The largest is 2048 (since ).
- The sequence is .
- There are 5 values.
- For :
- The smallest is 2018 (since ).
- The largest is 2050 (since ).
- The sequence is .
- There are 5 values.
- For :
- The smallest is 2021 (since ).
- The largest is 2045 (since ).
- The sequence is .
- There are 4 values.
7. Summing the Values:
- Total number of values is .
The final answer is