2018 AMC 10A Problem 17

Test the candidates for the minimum from smallest to largest. ($1$ is impossible since everything is a multiple of $1$.)

Minimum $2$. Then $4, 6, 8, 10, 12$ are excluded, leaving $3, 5, 7, 9, 11$ as candidates for the other five elements. But $9$ is a multiple of $3$, so at most four of them can be used, giving a set of at most $5$ elements. Fails.

Minimum $3$. Then $6, 9, 12$ are excluded (and $1, 2$ are below the minimum), leaving $4, 5, 7, 8, 10, 11$. Within these, $4 \mid 8$ and $5 \mid 10$, so at most one of $\{4, 8\}$ and one of $\{5, 10\}$ can be used: at most $1 + 1 + 2 = 4$ more elements, total $5$. Fails.

Minimum $4$. Exclude $8$ and $12$; choose from $5, 6, 7, 9, 10, 11$. Take $S = \{4, 5, 6, 7, 9, 11\}$. Check every pair: $6, 7, 9, 11$ are not multiples of $4$ or $5$; $9$ and $11$ are not multiples of $6$ or $7$; $11$ is not a multiple of $9$. Valid.

The answer is $\boxed{\textbf{(C)}\ 4}$.

A small minimum is expensive: every multiple of it is banned, and the survivors still have divisibility conflicts among themselves. The efficient argument is a capacity count: after banning the multiples of the minimum, group the remaining candidates into "divisor chains" such as $\{3, 9\}$ or $\{4, 8\}$, from which at most one element can be picked, and see whether five elements are still available. When they are not, move the minimum up and try again, ending with an explicit set.

• Only checking that the chosen set avoids multiples of the minimum, forgetting pairs like 3 and 9 or 5 and 10 among the other elements.
• Stopping after showing $2$ fails and guessing $3$, without carrying out the same capacity check for $3$.