2018 AMC 10A Problem 17

Problem 17 of 25IntermediateAlgebra Number Theory

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?

Show solution

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

8

and

5

10.

Either way, the maximum number of elements that we can include is

5,

3

cannot be the smallest element. Starting with

4,

we can include

6, 7, 9

and

11.

Finally, we can add either

5

10,

creating a

6

-element set. Thus, C is the correct answer.