🇺🇸 AMC 8 ⇄ switch contest
1996 AMC 8 Stretch

Problem 3

Problem 3 · AMC 8 Stretch Stretch
Logic & Word Problems Number Theory work-backwardaccount-for-all-possibilities
Same take-away game (pile of \(27\), take \(1\) to \(4\) each turn). New rule: when all counters are gone, the player who has collected an EVEN number of counters wins. (This is harder — you must keep track of both how many you leave AND whether your own pile is even or odd.) What should your first move be?
Show answer
Answer: Go first and take 2
Show hints
Hint 1 of 4
This time your position depends on two things at once: how many counters you leave, and whether your own collected pile is even or odd. Track both.
Still stuck? Show hint 2 →
Hint 2 of 4
Start at the end. If you already hold an EVEN number and you can leave \(0\) or \(1\), you win. So aim to finish holding an even amount.
Still stuck? Show hint 3 →
Hint 3 of 4
If you hold an ODD number and leave \(5\), check all four replies: they take \(1\), you take \(3\); take \(2\), you take \(3\); take \(3\), you take \(1\); take \(4\), you take \(1\). In every case your pile flips to EVEN and you leave a deadly \(0\) or \(1\).
Show solution
Approach: Working backward while tracking two states (counters left and parity of your pile)
  1. Here you win based on whether YOUR OWN pile is even at the end, so you track two things: the number you leave, and the even/odd state of what you hold.
  2. When you hold an ODD number, leaving \(5\) wins. Check every reply: take \(1\) then you take \(3\); take \(2\) then you take \(3\); take \(3\) then you take \(1\); take \(4\) then you take \(1\). Each time you add enough so your pile becomes EVEN and you leave a fatal \(0\) or \(1\).
  3. When you hold an EVEN number, the safe leaves come in pairs. The base pair is \(0, 1\) (you already won) and the next pair is \(6, 7\). Continuing by working backward gives — even pile: leave \(0, 1, 6, 7, 12, 13, 18, 19, 24, 25\); odd pile: leave \(5, 11, 17, 23\).
  4. From \(27\), the one good first move is to take \(2\): now you hold \(2\) (even) and have left \(25\), which is on the even list. After that, always land on the list matching your current parity.
Mark: · log in to save
↑