Question

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

$2$

$3$

$4$

$5$

$7$

Solution:

We proceed by casing on possible values for $S:$

$1$ cannot be the smallest element since that would mean that no other number can be in the set.

$2$ cannot be the smallest element since we would have to include every odd number except $1.$ This would make $3$ and $9$ violate the rule.

Let $3$ be the smallest element. Then we can include $7$ and $11.$ We can finally include either $4$ or $8$ and $5$ or $10.$

Either way, the maximum number of elements that we can include is $5,$ so $3$ cannot be the smallest element.

Starting with $4,$ we can include $6, 7, 9$ and $11.$ Finally, we can add either $5$ or $10,$ creating a $6$ -element set.

Thus, C is the correct answer.

2018 AMC 10A Problem 17

Solution:

Problem 17 in Other Years