Difference between revisions of "2018 AMC 10A Problems/Problem 17"

m (Problem: typo)
(9 intermediate revisions by 8 users not shown)
Line 5: Line 5:
  
 
== Solution ==
 
== Solution ==
If we start with <math>1</math>, we can include nothing else, so that won't work.
+
If we start with <math>1</math>, we can include nothing else, so that won't work. (Also note that <math>1</math> is not an answer choice)
  
 
If we start with <math>2</math>, we would have to include every odd number except <math>1</math> to fill out the set, but then <math>3</math> and <math>9</math> would violate the rule, so that won't work.
 
If we start with <math>2</math>, we would have to include every odd number except <math>1</math> to fill out the set, but then <math>3</math> and <math>9</math> would violate the rule, so that won't work.
  
Experimentation with <math>3</math> shows it's likewise impossible. You can include <math>7</math>, <math>11</math>, and either <math>5</math> or <math>10</math> (which are always safe). But after adding either <math>4</math> or <math>8</math> we have nowhere else to go.
+
Experimentation with <math>3</math> shows it's likewise impossible. You can include <math>7</math>, <math>11</math>, and either <math>5</math> or <math>10</math> (which are always safe). But after adding either <math>4</math> or <math>8</math> we have no more places to go.
  
 
Finally, starting with <math>4</math>, we find that the sequence <math>4,5,6,7,9,11</math> works, giving us <math>\boxed{\textbf{(C)} \text{ 4}}</math>.
 
Finally, starting with <math>4</math>, we find that the sequence <math>4,5,6,7,9,11</math> works, giving us <math>\boxed{\textbf{(C)} \text{ 4}}</math>.
(Random_Guy)
+
 
 +
==Solution 2==
 +
We know that all the odd numbers (except 1) can be used.
 +
 
 +
<math>3, 5, 7, 9, 11</math>
 +
 
 +
Now we have 7 to choose from for the last number (out of <math>1, 2, 4, 6, 8, 10, 12</math>). We can eliminate 1, 2, 10, and 12, and we have <math>4, 6, 8</math> 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 <math>9</math>, none of the numbers would work, but if we take out <math>3</math>, we get:
 +
 
 +
<math>4, 5, 6, 7, 9, 11</math>
 +
 
 +
So the least number is <math>4</math>, so the answer is <math>\boxed{\textbf{(C)} \text{ 4}}</math>.
 +
 
 +
 
 +
==Solution 3==
 +
We can get the multiples for the numbers in the original set with multiples in the same original set
 +
 
 +
<math>1:</math> <math>\text{all}</math> <math>\text{numbers}</math> <math>\text{within}</math> <math>\text{range}</math>
 +
 
 +
<math>2: 4,6,8,10,12</math>
 +
 
 +
<math>3: 6,9,12</math>
 +
 
 +
<math>4: 8,12</math>
 +
 
 +
<math>5: 10</math>
 +
 
 +
<math>6: 12</math>
 +
 
 +
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 <math>4</math>, we can get <math>4,5,6,7,9,11</math>. So <math>4</math> works.
 +
Trying <math>3</math> won't work, so the least is <math>4</math>. This means the answer is <math>\boxed{\textbf{(C) } 4}</math>
 +
 
 +
 
 +
==Video Solution==
 +
https://youtu.be/M22S82Am2zM
 +
 
  
 
==See Also ==
 
==See Also ==
Line 18: Line 54:
 
{{AMC12 box|year=2018|ab=A|num-b=11|num-a=13}}
 
{{AMC12 box|year=2018|ab=A|num-b=11|num-a=13}}
 
{{MAA Notice}}
 
{{MAA Notice}}
 +
 +
[[Category:Introductory Number Theory Problems]]

Revision as of 17:02, 26 January 2020

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. (Also note that $1$ is not an answer choice)

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}}$.

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}}$.


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


Video Solution

https://youtu.be/M22S82Am2zM


See Also

2018 AMC 10A (ProblemsAnswer KeyResources)
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 (ProblemsAnswer KeyResources)
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. AMC logo.png