AMC 10 · 2012 · #17

Grade 7 number-theory
Archetype Pair-Sum Invariant └ Sub-archetype Forbidden-Complement Selection
modular-arithmeticset-partitionoptimization-counting identify-subproblemsextremal-constructionsystematic-enumeration ↑ Prerequisites: modular-arithmetic
📏 Medium solution 💡 3 insights
Problem
No two chosen numbers may add to a multiple of five. Find the largest possible choice.

Pick an answer.

(A)
10
(B)
13
(C)
15
(D)
16
(E)
18
How to solve
Strategy Organize Information in More Ways

Listed as 1,2,3,…,30 the numbers say nothing useful, because the rule is about sums being multiples of 5. Tool #15 (Organize Information in More Ways) is the whole move: regroup the same 30 numbers by their remainder on division by 5. Tool #4 (Introduce a Variable) justifies that regrouping — write x=5q+r and the remainders alone control x+y. Tool #2 (Make a Systematic List) then finds every remainder pair that is banned, a list of only three entries. Tool #14 (Extreme Principle) turns those three bans into a ceiling on |S|. The last step is the one that is easy to skip: a ceiling only says a size is impossible to exceed, so an explicit set reaching the ceiling must be exhibited before the ceiling can be called the answer.

1STEP 1

Regroup the pool by remainder

The pool regroups into five remainder families.

R₀={5,10,15,20,25,30}, R₁={1,6,11,16,21,26}, R₂={2,7,12,17,22,27}, R₃={3,8,13,18,23,28}, R₄={4,9,14,19,24,29}
2STEP 2

Only remainders decide the sum

Only the remainders decide the sum.

x+y=(5q₁+a)+(5q₂+b)=5(q₁+q₂)+(a+b) → 5 ∣ x+y ⇔ 5 ∣ a+b
3STEP 3

List the banned label pairs

That gives exactly three banned pairings.

banned pairs of labels = {(0,0), (1,4), (2,3)}
4STEP 4

Turn the bans into a ceiling

The bans cap the choice at 13.

|S|=a₀+(a₁+a₄)+(a₂+a₃) ≤ 1+6+6=13
5STEP 5

Show that 13 is reached

A real choice reaches that cap, choice (B).

S={1,6,11,16,21,26}∪{2,7,12,17,22,27}∪{5}, |S|=6+6+1=13
Answer
13
Spot-check the exhibited set: 1+2=3, 6+21=27, 5+27=32, 16+22=38, 11+26=37 — none divisible by 5, and the only multiple of 5 inside is the single element 5, so no pair of multiples of 5 exists. The bound and the construction agree at 13, so 13 is the true maximum. The wrong choices come from predictable slips. Choice (E) 18 is 6+6+6, taking three whole groups and forgetting that R₀ pairs with itself (5+10=15 breaks it). Choice (C) 15 is the tempting half of 30 but nothing in the problem makes half achievable. Choice (A) 10 undercounts by taking only 5 from each usable group. Choice (D) 16 has no consistent story at all. The near-miss worth naming is 12: a solver who discards R₀ entirely stops at 6+6, missing that the rule bans only pairs of distinct elements, so one lone multiple of 5 is still allowed.
💡Key takeaway

Sort 1 to 30 by remainder after dividing by 5: you may keep a whole remainder group, but never both of a pair that adds to 5, and only one multiple of 5 — that gives 6+6+1=13.

  • Regroup the pool by remainder
  • Only remainders decide the sum
  • List the banned label pairs
  • Turn the bans into a ceiling
  • Show that 13 is reached

More like this

Same archetype — closest grade level first.