Maths Olympiad Prep

Library / /434 of 520

Combinatorics Difficulty 7.4 National olympiad, round 2 Find the answer

Two players play a game on a pile of nn beans. On each player's turn, they may take exactly 11, 44, or 77 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 nn between 20142014 and 20502050 (inclusive) does the second player win?

A number or a short expression. Spacing and $ signs are ignored.

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 n n (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 W W and a losing position by L L .
- 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:
- n=0 n = 0 : Losing position (L L ) because the player to move cannot make a move.
- n=1 n = 1 : Winning position (W W ) because the player can take the last bean and win.
- n=2 n = 2 : Winning position (W W ) because the player can take 1 bean, leaving 1 bean for the opponent, who then loses.
- n=3 n = 3 : Winning position (W W ) because the player can take 1 bean, leaving 2 beans for the opponent, who then loses.
- n=4 n = 4 : Winning position (W W ) because the player can take 4 beans and win.
- n=5 n = 5 : Winning position (W W ) because the player can take 4 beans, leaving 1 bean for the opponent, who then loses.
- n=6 n = 6 : Winning position (W W ) because the player can take 4 beans, leaving 2 beans for the opponent, who then loses.
- n=7 n = 7 : Winning position (W W ) because the player can take 7 beans and win.
- n=8 n = 8 : Losing position (L L ) 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 n=0 n = 0 and n=8 n = 8 are losing positions.
- We can generalize this pattern: n0(mod8) n \equiv 0 \pmod{8} and n8(mod8) n \equiv 8 \pmod{8} are losing positions.
- Extending this pattern, we find that n0,2,5(mod8) n \equiv 0, 2, 5 \pmod{8} are losing positions.

5. **Counting the Values of n n Between 2014 and 2050:**
- We need to count the number of integers n n in the range 2014n2050 2014 \leq n \leq 2050 such that n0,2,5(mod8) n \equiv 0, 2, 5 \pmod{8} .

6. Finding the Specific Values:
- For n0(mod8) n \equiv 0 \pmod{8} :
- The smallest n n is 2016 (since 20160(mod8) 2016 \equiv 0 \pmod{8} ).
- The largest n n is 2048 (since 20480(mod8) 2048 \equiv 0 \pmod{8} ).
- The sequence is 2016,2024,2032,2040,2048 2016, 2024, 2032, 2040, 2048 .
- There are 5 values.

- For n2(mod8) n \equiv 2 \pmod{8} :
- The smallest n n is 2018 (since 20182(mod8) 2018 \equiv 2 \pmod{8} ).
- The largest n n is 2050 (since 20502(mod8) 2050 \equiv 2 \pmod{8} ).
- The sequence is 2018,2026,2034,2042,2050 2018, 2026, 2034, 2042, 2050 .
- There are 5 values.

- For n5(mod8) n \equiv 5 \pmod{8} :
- The smallest n n is 2021 (since 20215(mod8) 2021 \equiv 5 \pmod{8} ).
- The largest n n is 2045 (since 20455(mod8) 2045 \equiv 5 \pmod{8} ).
- The sequence is 2021,2029,2037,2045 2021, 2029, 2037, 2045 .
- There are 4 values.

7. Summing the Values:
- Total number of values is 5+5+4=14 5 + 5 + 4 = 14 .

The final answer is 14\boxed{14}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.