AMC 10 · 2015 · #22
Grade 9 countingpatternPick an answer.
Tool #7 (Identify Subproblems) is the engine: a legal string ends in a block of 1, 2, or 3 identical letters, and chopping that block off leaves a shorter legal string, which turns one huge count into three smaller counts of the same kind. Tool #16 (Change Focus) first replaces 'count everything' with 'count only the strings ending in A', which the A⇔ B symmetry makes exactly half the total. Tool #9 (Solve an Easier Related Problem) trades the impossible question 'what is S(2015)' for the small one 'what is its remainder', and pins down exactly how much precision that needs. Tool #11 (Work Backwards) runs the recurrence in reverse to pin down a legal index-0 starting value, so the later index arithmetic lines up. Tool #5 (Look for a Pattern) reduces every term modulo 2 and modulo 3, where the sequence repeats after 4 and 13 terms. Tool #3 (Eliminate Possibilities) then sweeps the six residues mod 6 and keeps the only survivor.
Split by the last letter
Symmetry makes the two endings equal.
The rule treats the two letters identically, so legal strings pair off and exactly half of them end in A.
7.SP.C.8Change Focus Count The ComplementPeel off the final block
Peeling the last block gives a recursion.
The only thing the rule cares about at the end of a string is how long the last block is, and that length has just three options.
9.F-BF.A.1Identify SubproblemsTurn it into one sequence
It closes into one sequence.
One rule that reaches back three steps replaces an impossible direct count.
9.F-BF.A.1Identify SubproblemsFix the starting values
The starting values are set by hand.
A backward step of the same rule is the honest way to create an index-0 term instead of guessing one.
9.F-IF.A.3Work BackwardsDecide what precision is needed
Only a small remainder needs following.
Doubling turns a remainder mod 6 straight into a remainder mod 12, so mod 6 is all the accuracy the answer needs.
6.EE.A.3Solve An Easier Related ProblemModulo 2: period 4
One modulus repeats every four terms.
The recurrence has a three-term memory, so once three consecutive remainders repeat, the whole sequence loops.
Because the rule reaches back three steps, the whole sequence loops once three consecutive remainders repeat.
▸ Why?
Three consecutive values decide everything that follows, so a repeat of them restarts the same run.
▸ Why?
Only finitely many remainder triples exist, so a repeat has to happen and the period is a real number.
Modulo 3: period 13
The other repeats every thirteen.
Landing on a multiple of the period sends the index right back to the start of the cycle.
6.NS.B.2Look For A PatternCombine into one residue mod 6
Combining them pins one residue.
Two coprime moduli lock together with no overlap, so their two remainders name a single class mod 6.
6.NS.B.4Eliminate PossibilitiesDouble it and read the remainder
Doubling gives 8, choice (D).
The doubling is the last move, so the mod-6 answer converts straight into the mod-12 answer.
7.NS.A.2Solve An Easier Related ProblemCount by how the string ends, turn that into a rule reaching back three steps, then track only the remainders — they run in a short cycle you can land on exactly.
- Split by the last letter
- Peel off the final block
- Turn it into one sequence
- Fix the starting values
- Decide what precision is needed
- Modulo 2: period 4
- Modulo 3: period 13
- Combine into one residue mod 6
- Double it and read the remainder