Question

Let $S$ be a set of $6$ integers taken from $\{1, 2, \ldots, 12\}$ with the property that if $a$ and $b$ are elements of $S$ with $a \lt b,$ then $b$ is not a multiple of $a.$ What is the least possible value of an element of $S?$

$2$

$3$

$4$

$5$

$7$

Answer: C

Concepts:divisibility pigeonhole principle extremal argument

Difficulty rating: 1630

Solution:

Partition $\{1, \ldots, 12\}$ into the six divisibility chains $\{1,2,4,8\},$ $\{3,6,12\},$ $\{5,10\},$ $\{7\},$ $\{9\},$ $\{11\}.$ Since no element of $S$ may divide another, at most one comes from each chain; needing $6$ elements forces exactly one from each, so $7, 9, 11 \in S.$

Because $9 \in S,$ $3 \notin S,$ so the second chain contributes $6$ or $12,$ and then neither $1$ nor $2$ can be chosen from the first chain (they divide $6$ and $12$ ). Taking $4$ from the first chain works: $S = \{4, 5, 6, 7, 9, 11\}$ has the property. Hence the least possible element is $4.$

Thus, the correct answer is C.

2018 AMC 12A Problem 12

Answer: C

Difficulty rating: 1630

Solution:

Problem 12 in Other Years