AMC 10 · 2013 · #20

Grade 7 countingnumber-theory

Archetype Small-Domain Constrained Search └ Sub-archetype Sum-Target Search

modular-arithmeticsymmetry-argumentpair-counting identify-subproblemsconvert-to-algebrasystematic-enumeration ↑ Prerequisites: modular-arithmetic

📏 Long solution 💡 4 insights

Problem

A beating relation wraps around, and three items must beat each other in a loop. Count the loops.

Pick an answer.

(A)

810

(B)

855

(C)

900

(D)

950

(E)

988

How to solve

Strategy Organize Information in More Ways

The definition of succ looks like two unrelated rules glued together, and that is what makes the problem hard. The single most useful move is to rewrite those two clauses as one rule. The magic number is 19: the second clause is exactly what the first clause becomes after adding 19. So I bend the list 1..19 into a circle of 19 points and read a succ b as one short forward hop. Then I name the three hop lengths, show that three hops around a circle must close up after exactly one lap, and count the hop lengths that do it. I check the count both forwards (every loop gives such hops) and backwards (every such choice of hops rebuilds a real loop), because only then is the count exact and not just an upper bound.

1STEP 1

Fuse the two clauses into one

The two clauses fuse into one remainder rule.

a succ b ⇔ (a-b) mod 19 ∈ {1,2,…,9}

2STEP 2

Bend the list into a 19-circle

That bends the list into a circle.

positions 1,2,…,19 on a circle; a succ b ⇔ a is 1..9 steps ahead of b

3STEP 3

Name the three hop lengths

Three hops describe the whole loop.

m ≡ x-y, n ≡ y-z, p ≡ z-x (mod 19), m,n,p ∈ {1,…,9}, m+n+p ≡ 0 (mod 19)

4STEP 4

Squeeze the total to exactly one lap

Their total must be exactly one lap.

3 ≤ m+n+p ≤ 27 and 19 ∣ m+n+p → m+n+p = 19 → p = 19-m-n, m+n ≥ 10

5STEP 5

Rebuild the loop to prove nothing is lost

Rebuilding shows nothing is lost.

(x,m,n) ⟷ (x, y, z) with y ≡ x-m, z ≡ x-m-n (mod 19)

6STEP 6

List the hop pairs that work

There are 45 workable hop pairs.

#{(m,n): 1 ≤ m,n ≤ 9, m+n ≥ 10} = 1+2+…+9 = 45

7STEP 7

Multiply by the 19 starting points

Times the starting points gives 855.

19 × 45 = 855

Answer

855

Two independent checks. First, symmetry forces divisors. Adding 1 to all three numbers around the 19-circle turns a loop into a loop, and 19 is prime with no loop fixed by the shift, so the loops split into groups of 19 and the answer must be a multiple of 19. Rotating the roles, (x, y, z) to (y, z, x), also keeps a loop a loop, and since x, y, z are distinct these groups have size 3, so the answer is a multiple of 3 as well. Hence 57 divides the answer. Of the five choices only 855 = 57 × 15 passes, since 810, 900, 950 and 988 fail one test or the other. Second, size sanity: for distinct a, b exactly one of a succ b and b succ a holds, so a random ordered triple of distinct numbers should form a loop about one time in eight; there are 19 × 18 × 17 = 5814 such triples, and 5814 divided by 8 is about 727, the same order of magnitude as 855. A spot check also works: (x, y, z) = (1, 11, 6) gives 11 - 1 = 10 ＞ 9 so 1 succ 11, then 11 - 6 = 5 so 11 succ 6, then 6 - 1 = 5 so 6 succ 1.

💡Key takeaway

Bend 1 through 19 into a circle and the odd two-part rule becomes one sentence: you are ahead by a hop of 1 to 9 — and three such hops that return home must add up to exactly one lap of 19.

Fuse the two clauses into one
Bend the list into a 19-circle
Name the three hop lengths
Squeeze the total to exactly one lap
Rebuild the loop to prove nothing is lost
List the hop pairs that work
Multiply by the 19 starting points