2018 AMC 10A Problems/Problem 17

Problem

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?$

$\textbf{(A)}\ 2\qquad\textbf{(B)}\ 3\qquad\textbf{(C)}\ 4\qquad\textbf{(D)}\ 5\qquad\textbf{(E)}\ 7$

Solution

If we start with $1$ , we can include nothing else, so that won't work.

If we start with $2$ , we would have to include every odd number except $1$ to fill out the set, but then $3$ and $9$ would violate the rule, so that won't work.

Experimentation with $3$ shows it's likewise impossible. You can include $7$ , $11$ , and either $5$ or $10$ (which are always safe). But after adding either $4$ or $8$ we have no more places to go.

Finally, starting with $4$ , we find that the sequence $4,5,6,7,9,11$ works, giving us $\boxed{\textbf{(C)} \text{ 4}}$ . (Random_Guy)

Solution 2

We know that all the odd numbers (except 1) can be used.

$3, 5, 7, 9, 11$

Now we have 7 to choose from for the last number (out of $1, 2, 4, 6, 8, 10, 12$ ). We can eliminate 1, 2, 10, and 12, and we have $4, 6, 8$ to choose from. But wait, 9 is a multiple of 3! Now we have to take out either 3 or 9 from the list. If we take out $9$ , none of the numbers would work, but if we take out $3$ , we get:

$4, 5, 6, 7, 9, 11$

So the least number is $4$ , so the answer is $\boxed{\textbf{(C)} \text{ 4}}$ .

-Baolan

Solution 3

We can get the multiples for the numbers in the original set with multiples in the same original set

$1:$ $\text{all}$ $\text{numbers}$ $\text{within}$ $\text{range}$

$2: 4,6,8,10,12$

$3: 6,9,12$

$4: 8,12$

$5: 10$

$6: 12$

It will be safe to start with 5 or 6 since they have the smallest number of multiples as listed above, but since the question asks for the least, it will be better to try others.

Trying $4$ , we can get $4,5,6,7,9,11$ . So $4$ works. Trying $3$ won't work, so the least is $4$ . This means the answer is $\boxed{\textbf{(C) } 4}$

~OlutosinNGA

2018 AMC 10A (Problems • Answer Key • Resources)
Preceded by Problem 16	Followed by Problem 18
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

2018 AMC 12A (Problems • Answer Key • Resources)
Preceded by Problem 11	Followed by Problem 13
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

Page

Toolbox

Search

2018 AMC 10A Problems/Problem 17

Contents

Problem

Solution

Solution 2

Solution 3

See Also