2018 AMC 10A Problem 17

This asks for the least possible smallest number, so there are two halves: show that $1$, $2$ and $3$ cannot be the smallest number, and show that $4$ can.

Part 1: the smallest number cannot be $1$, $2$ or $3$.

1. Smallest number $1$. Every number is a multiple of $1$, so nothing else could join $1$. Impossible.
2. Smallest number $2$. Then $4, 6, 8, 10, 12$ are all multiples of $2$ and are ruled out. The other five members must come from $3, 5, 7, 9, 11$. That is exactly five numbers, but $9$ is a multiple of $3$, so they cannot all be used. At most four join $2$, giving at most $5$ numbers. Not enough.
3. Smallest number $3$. Then $6, 9, 12$ are ruled out, and $1, 2$ are too small. The other five members must come from $4, 5, 7, 8, 10, 11$. But $8$ is a multiple of $4$, so at most one of $4$ and $8$ can be used. Likewise at most one of $5$ and $10$. So at most $1 + 1 + 2 = 4$ of these numbers (one from $\{4, 8\}$, one from $\{5, 10\}$, plus $7$ and $11$), and at most $5$ numbers in all. Not enough.

Part 2: the smallest number can be $4$.

4. Take $S = \{4, 5, 6, 7, 9, 11\}$. Check each number against the smaller ones:
- $5, 6, 7, 9, 11$ are not multiples of $4$.
- $6, 7, 9, 11$ are not multiples of $5$.
- $7, 9, 11$ are not multiples of $6$.
- $9, 11$ are not multiples of $7$.
- $11$ is not a multiple of $9$.

No number is a multiple of a smaller one, and $S$ has $6$ numbers. It works.

The smallest number cannot be below $4$, and $4$ is possible.

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

A small number is costly: every multiple of it is banned. After banning those, look for pairs among the leftover numbers where one is a multiple of the other ($3$ and $9$, $4$ and $8$, $5$ and $10$). You can use only one number from each such pair, so counting pairs tells you the most you can pick. For a "least possible" question, always finish by showing a set that actually works.