AMC 10 · 2018 · #17
Easy mode Grade 4Pick 6 different numbers from 1 to 12. Follow one rule: no number you pick can be a multiple of another number you pick. (For example, you cannot pick both 3 and 6, because 6 is a multiple of 3.)
Out of all the ways to do this, what is the smallest the lowest number can be?
Pick an answer.
AMC 10 2018 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: Pick a set $S$ of $6$ numbers from $\{1,2,\dots,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?
Givens: $S$ has exactly $6$ elements, all chosen from $\{1,2,\dots,12\}$; If $a<b$ are both in $S$, then $b$ is not a multiple of $a$; Answer choices for the least element: $2,\ 3,\ 4,\ 5,\ 7$
Unknowns: The smallest value that the least element of $S$ can take
Understand
Restated: Pick a set $S$ of $6$ numbers from $\{1,2,\dots,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?
Givens: $S$ has exactly $6$ elements, all chosen from $\{1,2,\dots,12\}$; If $a<b$ are both in $S$, then $b$ is not a multiple of $a$; Answer choices for the least element: $2,\ 3,\ 4,\ 5,\ 7$
Plan
Primary tool: #14 Extreme Principle
Secondary: #6 Guess and Check, #3 Eliminate Possibilities, #2 Make a Systematic List
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.
Execute — Answer: C
4.OA.B.4 Step 1 Search from the bottom up
- We want the smallest the least element can be, so test candidate smallest values in increasing order and take the first that works.
- The value $1$ is out: $1$ divides every number, so if $1\in S$ then any other element would be a multiple of $1$, breaking the rule.
- So the least element is at least $2$; we check $2$, then $3$, then $4$.
💡 To find the smallest possible start, try the smallest values first and stop at the first that works.
4.OA.B.4 Step 2 Try smallest $=2$
- If $2$ is the smallest element, then every even number $4,6,8,10,12$ is a multiple of $2$ and is banned.
- Only the odd numbers $3,5,7,9,11$ are left to fill the other $5$ slots.
- But $9$ is a multiple of $3$, so $3$ and $9$ cannot both appear; at most $4$ of those $5$ odds survive.
- That gives at most $1+4=5$ elements, short of $6$.
- So $2$ cannot be the smallest.
💡 Starting at $2$ throws away every even number, leaving too few to reach six.
4.OA.B.4 Step 3 Try smallest $=3$
- If $3$ is the smallest, drop its multiples $6,9,12$.
- The numbers above $3$ still allowed are $4,5,7,8,10,11$.
- But $8$ is a multiple of $4$ and $10$ is a multiple of $5$, so each of those pairs can keep only one member.
- At most $4$ of the six survive, again giving at most $1+4=5$ elements.
- So $3$ cannot be the smallest either.
💡 Each divides-pair forces a sacrifice, so the allowed list keeps coming up one short.
4.OA.B.4 Step 4 Try smallest $=4$ and finish
- If $4$ is the smallest, drop its multiples $8,12$.
- The numbers above $4$ still allowed are $5,6,7,9,10,11$.
- The only divides-pair here is $5$ and $10$ (since $10=2\cdot 5$), so drop $10$ and keep $5,6,7,9,11$ — five numbers with no one a multiple of another ($9=3^2$ but $3\notin S$, and $6$'s multiple $12$ is gone).
- Add the $4$ to get $S=\{4,5,6,7,9,11\}$: six elements, none a multiple of a smaller one.
- So $4$ works.
- Since $2$ and $3$ both failed, the least possible value of an element in $S$ is $4$, choice $\textbf{(C)}$.
💡 Once $2$ and $3$ are ruled out, the first value that lets six fit is the answer.
4.OA.B.4 We want the smallest the least element can be, so test candidate smallest values 4.OA.B.4 If $2$ is the smallest element, then every even number $4,6,8,10,12$ is a multip 4.OA.B.4 If $3$ is the smallest, drop its multiples $6,9,12$. The numbers above $3$ still 4.OA.B.4 If $4$ is the smallest, drop its multiples $8,12$. The numbers above $4$ still a Review
Reasonableness: 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 $\textbf{(C)}$.
Alternative: Tool #2 (Make a Systematic List): split $\{1,\dots,12\}$ into six divisor-chains such as $\{1,2,4,8\},\{3,6,12\},\{5,10\},\{7\},\{9\},\{11\}$. A valid $S$ takes exactly one number per chain. To keep the smallest element low you avoid the chain-tops, and working through the chains shows the smallest element can be $4$ but no lower, again giving $\textbf{(C)}$.
CCSS standards used (min grade 4)
4.OA.B.4Find all factor pairs and recognize multiples; determine prime or composite (Deciding for each candidate smallest value which larger numbers are multiples of it (so banned), spotting divides-pairs like $3\mid 9$, $4\mid 8$, $5\mid 10$, and confirming $\{4,5,6,7,9,11\}$ has no element that is a multiple of a smaller one.)
⭐ 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 $\textbf{(C)}$.
⭐ 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 $\textbf{(C)}$.
More like this
Same archetype — closest grade level first.