AMC 10 · 2018 · #17

Grade 4 number-theory
Archetype Small-Domain Constrained Search └ Sub-archetype Answer-Choice Plug-In
multiplesdivisibility-rulesset-partitionfactors extremal-constructioncasework ↑ Prerequisites: multiplesdivisibility-rules
📏 Medium solution 💡 2 insights
📘 View easy version →
Problem
Pick a set S of 6 numbers from {1,2,…,12} so that no element of S is a multiple of a smaller element of S. Among all such sets, how small can the smallest element be?

Pick an answer.

(A)
2
(B)
3
(C)
4
(D)
5
(E)
7

AMC 10 2018 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve
Strategy Extreme Principle

The question asks for the least possible value of the smallest element, which is a minimize-the-boundary question — Tool #14 (Extreme Principle). The smart move is to test candidate smallest values from the bottom up (2, then 3, then 4) and stop at the first one that lets a full set of 6 be built. Tool #6 (Guess and Check): for each candidate smallest value, try to build a valid set of 6. Tool #2 (Make a Systematic List): after fixing the smallest element, list exactly which larger numbers are still allowed. Tool #3 (Eliminate Possibilities): the answer choices let us rule out 2 and 3, so the first choice that survives is the answer.

1STEP 1

Search from the bottom up

Since 1 divides everything it can't be in S, so the least element is at least 2 — test 2, then 3, then 4 and take the first that works.

1 ∣ n for every n, so 1∈ S forces a multiple pair → least element ≥ 2
2STEP 2

Try smallest =2

Start at 2 and every even number is banned; only odds 3,5,7,9,11 remain, but 3 divides 9, so at most 5 elements fit — short of six.

2∈ S→ allowed ={3,5,7,9,11}, but 3 ∣ 9→ at most 4 usable; 1+4=5 ＜ 6
3STEP 3

Try smallest =3

Start at 3, dropping 6,9,12; among 4,5,7,8,10,11 the pairs 4–8 and 5–10 each cost one, so at most 5 elements fit — still short.

3∈ S→ allowed ={4,5,7,8,10,11}, but 4 ∣ 8 and 5 ∣ 10→ at most 4 usable; 1+4=5 ＜ 6
4STEP 4

Try smallest =4 and finish

Start at 4: the set {4,5,6,7,9,11} gives six elements with no multiples, and since 2 and 3 failed, the least element is 4, choice (C).

S={4,5,6,7,9,11}; no a ∣ b for a ＜ b in S→ least element =4=(C)
Answer
4
The set {4,5,6,7,9,11} passes every check: scanning each pair, no larger number is a multiple of a smaller one, and it has exactly 6 elements with smallest 4. The lower values are genuinely blocked — both 2 and 3 topped out at 5 elements — so 4 is the smallest attainable least element, matching choice (C).
💡Key takeaway

Test the smallest start first: 2 and 3 leave too few non-multiples to reach six, but starting at 4 the set {4,5,6,7,9,11} fits, so the least element is 4, choice (C).

  • Search from the bottom up
  • Try smallest =2
  • Try smallest =3
  • Try smallest =4 and finish

More like this

Same archetype — closest grade level first.