AMC 10 · 2013 · #18
Grade 6 logicpatternPick an answer.
Nobody can play 2013 coins forward. But the end of the game is fully known — taking the last coin wins — so the outcome of every position can be pushed backwards from there: a position is a win for the player to move exactly when at least one legal move hands the opponent a position that is a loss for the opponent. Because the two players have different move sets, a position must be recorded as a pair (pile size, whose turn), and the two cases have to be tracked side by side. Running that backward sweep on small piles produces a table, and the table repeats with period 5. That repetition is the whole problem, and it must be proved rather than trusted: an observed pattern in the first ten rows says nothing about row 2013. So the plan is to read a characterisation off the table, write it in terms of the remainder n mod 5, and then prove it by strong induction, which is what upgrades "it looks periodic" into "it is periodic forever". Only then are 2013 and 2014 safe to reduce to remainders. Each pile size gets its own verdict for each possible first mover — four verdicts in all — because the answer choices distinguish 'X wins' from 'whoever goes first wins', and those two statements are settled by different data.
Name the positions
Each pile size has two positions to label.
Two players with different moves means every pile size really has two separate stories, so track both at once.
6.EE.A.2Introduce A VariableFill the small piles by hand
Small piles fill in by hand.
The endgame is small enough to settle by hand, and every later position is built only out of positions already settled.
4.OA.A.3Solve An Easier Related ProblemRead the pattern as remainders
The pattern reads as a remainder rule.
Barbara's moves change the pile by 2 or 4 and Jenna's by 1 or 3, and 2+3 = 4+1 = 5, so 5 is the natural block size to measure in.
The two players' moves make five the natural block size, so only the remainder after dividing by five matters.
▸ Why?
Each pair of moves adds up to the same block, so removing whole blocks changes nothing about who wins.
▸ Why?
The positions therefore repeat with that period, so a huge pile behaves exactly like its small leftover.
Prove Barbara's half by induction
Induction proves one player's half.
Barbara only ever wants one thing: to hand Jenna a pile that is a whole number of fives.
6.EE.A.3Work BackwardsProve Jenna's half by induction
The same argument covers the other half.
Jenna has two different steps available and between them they cover every bad residue for Barbara except one, so only a clean multiple of 5 can stop her.
6.EE.A.3Work BackwardsDivide 2013 and 2014 by 5
The two pile sizes leave remainders 3 and 4.
Two thousand coins behave exactly like the three or four coins left over after stripping away whole blocks of five.
4.NBT.B.6Work BackwardsMatch the two verdicts to a choice
That names the two verdicts, choice (B).
Every choice bundles two claims, so a choice dies as soon as either half of it is wrong.
4.OA.A.3Eliminate PossibilitiesBarbara takes 2 or 4 and Jenna takes 1 or 3, and both pairs add to 5, so all that matters is the pile's remainder when divided by 5 and whose turn it is.
- Name the positions
- Fill the small piles by hand
- Read the pattern as remainders
- Prove Barbara's half by induction
- Prove Jenna's half by induction
- Divide 2013 and 2014 by 5
- Match the two verdicts to a choice