2018 AMC 12A Problem 12

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?

Show solution

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

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.