Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2018 AMC 10A Problems/Problem 17"
 
(23 intermediate revisions by 7 users not shown)
Line 1: Line 1:
 +
{{duplicate|[[2018 AMC 10A Problems/Problem 17|2018 AMC 10A #17]] and [[2018 AMC 12A Problems/Problem 12|2018 AMC 12A #12]]}}
 +
 
== Problem ==
 
== Problem ==
−
Let <math>S</math> be a set of 6 integers taken from <math>\{1,2,\dots,12\}</math> with the property that if <math>a</math> and <math>b</math> are elements of <math>S</math> with <math>a<b</math>, then <math>b</math> is not a multiple of <math>a</math>. What is the least possible value of an element in <math>S?</math>
+
Let <math>S</math> be a set of <math>6</math> integers taken from <math>\{1,2,\dots,12\}</math> with the property that if <math>a</math> and <math>b</math> are elements of <math>S</math> with <math>a<b</math>, then <math>b</math> is not a multiple of <math>a</math>. What is the least possible value of an element in <math>S</math>?
  
 
<math>\textbf{(A)}\ 2\qquad\textbf{(B)}\ 3\qquad\textbf{(C)}\ 4\qquad\textbf{(D)}\ 5\qquad\textbf{(E)}\ 7</math>
 
<math>\textbf{(A)}\ 2\qquad\textbf{(B)}\ 3\qquad\textbf{(C)}\ 4\qquad\textbf{(D)}\ 5\qquad\textbf{(E)}\ 7</math>
  
−
== Solution ==
+
== Solution 1 ==
−
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)
+
We start with <math>2</math> because <math>1</math> is not an answer choice. 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,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 valid numbers.
  
−
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)}\ 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>.
+
==Solution 2==
 +
We know that all odd numbers except <math>1,</math> namely <math>3, 5, 7, 9, 11,</math> can be used.
  
−
==Solution 2==
+
Now we have <math>7</math> possibilities to choose from for the last number (out of <math>1, 2, 4, 6, 8, 10, 12</math>). We can eliminate <math>1, 2, 10,</math> and <math>12,</math> and we have <math>4, 6, 8</math> to choose from. However, <math>9</math> is a multiple of <math>3.</math> Now we have to take out either <math>3</math> or <math>9</math> 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 <cmath>4, 5, 6, 7, 9, 11.</cmath>
−
We know that all the odd numbers (except 1) can be used.
+
The least number is <math>4,</math> so the answer is <math>\boxed{\textbf{(C)}\ 4}.</math>
  
−
<math>3, 5, 7, 9, 11</math>
+
==Solution 3==
 +
We can get the multiples for the numbers in the original set with multiples in the same original set
 +
<cmath>\begin{align*}
 +
1&: \ \text{all elements of }\{1,2,\dots,12\} \\
 +
2&: \ 4,6,8,10,12 \\
 +
3&: \ 6,9,12 \\
 +
4&: \ 8,12 \\
 +
5&: \ 10 \\
 +
6&: \ 12
 +
\end{align*}</cmath>
 +
It will be safe to start with <math>5</math> or <math>6</math> 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.
  
−
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:
+
Trying <math>4,</math> we can get <math>4,5,6,7,9,11.</math> So <math>4</math> works.
 +
Trying <math>3,</math> it won't work, so the least is <math>4.</math> This means the answer is <math>\boxed{\textbf{(C)}\ 4}.</math>
  
−
<math>4, 5, 6, 7, 9, 11</math>
+
==Solution 4==
 +
We partition <math>\{1,2,\ldots,12\}</math> into six nonempty subsets such that for every subset, each element is a multiple of all elements less than or equal to itself: <cmath>\{1,2,4,8\}, \ \{3,6,12\}, \ \{5,10\}, \ \{7\}, \ \{9\}, \ \{11\}.</cmath>
 +
Clearly, <math>S</math> must contain exactly one element from each subset:
  
−
So the least number is <math>4</math>, so the answer is <math>\boxed{\textbf{(C)} \text{ 4}}</math>.
+
* For <math>\{5,10\},</math> we can select either <math>5</math> or <math>10.</math>
  
 +
* For <math>\{3,6,12\},</math> we can select either <math>6</math> or <math>12.</math> Recall that since <math>9\in S,</math> we cannot select <math>3.</math>
  
−
==Solution 3==
+
* For <math>\{1,2,4,8\},</math> we can select either <math>4</math> (provided that <math>12\not\in S</math>) or <math>8.</math> Recall that since either <math>6\in S</math> or <math>12\in S,</math> we can select neither <math>1</math> nor <math>2.</math>
−
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>
+
If <math>4\in S,</math> then the possibilities of <math>S</math> are <math>\{4,5,6,7,9,11\}</math> or <math>\{4,6,7,9,10,11\}.</math> So, the least possible value of an element in <math>S</math> is <math>\boxed{\textbf{(C)}\ 4}.</math>
  
−
<math>2: 4,6,8,10,12</math>
+
<u><b>Remark</b></u>
  
−
<math>3: 6,9,12</math>
+
There exist multiple such partitions of <math>\{1,2,\ldots,12\}</math> into six nonempty subsets, one of which is <cmath>\{1,2,6,12\}, \ \{3,9\}, \ \{4,8\}, \ \{5,10\}, \ \{7\}, \ \{11\}.</cmath>
 +
Regardless of which partition we use, we will conclude that to minimize the least element of <math>S,</math> the only possibilities for <math>S</math> are <math>\{4,5,6,7,9,11\}</math> or <math>\{4,6,7,9,10,11\}.</math>
  
−
<math>4: 8,12</math>
+
~MRENTHUSIASM
  
−
<math>5: 10</math>
+
==Solution 5==
  
−
<math>6: 12</math>
+
We start with 2 as 1 is not an answer option. Our set would be <math>\{2,3,5,7,11\}</math>. We realize we cannot add 12 to the set because 12 is a multiple of 3. Our set only has 5 elements, so starting with 2 won't work.
  
−
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.
+
We try 3 next. Our set becomes <math>\{3,4,5,7,11\}</math>. We run into the same issue as before so starting with 3 won't work.
  
−
Trying <math>4</math>, we can get <math>4,5,6,7,9,11</math>. So <math>4</math> works.
+
We then try 4. Our set becomes <math>\{4,5,6,7,9,11\}</math>. We see we have 6 elements with none being multiples of each other. Therefore our answer is <math>\boxed{\textbf{(C)}\ 4}.</math>
−
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>
 
  
 +
~[https://artofproblemsolving.com/wiki/index.php/User:South South]
  
 
==Video Solution==
 
==Video Solution==
 
https://youtu.be/M22S82Am2zM
 
https://youtu.be/M22S82Am2zM
  
 +
~IceMatrix
 +
 +
==Video Solution==
 +
https://youtu.be/QtqBEZAgXpk
 +
 +
~savannahsolver
  
 
==See Also ==
 
==See Also ==

Latest revision as of 02:29, 14 October 2023

The following problem is from both the 2018 AMC 10A #17 and 2018 AMC 12A #12, so both problems redirect to this page.

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 1

We start with $2$ because $1$ is not an answer choice. 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 valid numbers.

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

Solution 2

We know that all odd numbers except $1,$ namely $3, 5, 7, 9, 11,$ can be used.

Now we have $7$ possibilities 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. However, $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.\] The least number is $4,$ so the answer is $\boxed{\textbf{(C)}\ 4}.$

Solution 3

We can get the multiples for the numbers in the original set with multiples in the same original set \begin{align*} 1&: \ \text{all elements of }\{1,2,\dots,12\} \\ 2&: \ 4,6,8,10,12 \\ 3&: \ 6,9,12 \\ 4&: \ 8,12 \\ 5&: \ 10 \\ 6&: \ 12 \end{align*} 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,$ it won't work, so the least is $4.$ This means the answer is $\boxed{\textbf{(C)}\ 4}.$

Solution 4

We partition $\{1,2,\ldots,12\}$ into six nonempty subsets such that for every subset, each element is a multiple of all elements less than or equal to itself: \[\{1,2,4,8\}, \ \{3,6,12\}, \ \{5,10\}, \ \{7\}, \ \{9\}, \ \{11\}.\] Clearly, $S$ must contain exactly one element from each subset:

  • For $\{5,10\},$ we can select either $5$ or $10.$
  • For $\{3,6,12\},$ we can select either $6$ or $12.$ Recall that since $9\in S,$ we cannot select $3.$
  • For $\{1,2,4,8\},$ we can select either $4$ (provided that $12\not\in S$) or $8.$ Recall that since either $6\in S$ or $12\in S,$ we can select neither $1$ nor $2.$

If $4\in S,$ then the possibilities of $S$ are $\{4,5,6,7,9,11\}$ or $\{4,6,7,9,10,11\}.$ So, the least possible value of an element in $S$ is $\boxed{\textbf{(C)}\ 4}.$

Remark

There exist multiple such partitions of $\{1,2,\ldots,12\}$ into six nonempty subsets, one of which is \[\{1,2,6,12\}, \ \{3,9\}, \ \{4,8\}, \ \{5,10\}, \ \{7\}, \ \{11\}.\] Regardless of which partition we use, we will conclude that to minimize the least element of $S,$ the only possibilities for $S$ are $\{4,5,6,7,9,11\}$ or $\{4,6,7,9,10,11\}.$

~MRENTHUSIASM

Solution 5

We start with 2 as 1 is not an answer option. Our set would be $\{2,3,5,7,11\}$. We realize we cannot add 12 to the set because 12 is a multiple of 3. Our set only has 5 elements, so starting with 2 won't work.

We try 3 next. Our set becomes $\{3,4,5,7,11\}$. We run into the same issue as before so starting with 3 won't work.

We then try 4. Our set becomes $\{4,5,6,7,9,11\}$. We see we have 6 elements with none being multiples of each other. Therefore our answer is $\boxed{\textbf{(C)}\ 4}.$

~South

Video Solution

https://youtu.be/M22S82Am2zM

~IceMatrix

Video Solution

https://youtu.be/QtqBEZAgXpk

~savannahsolver

See Also

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_AMC_10A_Problems/Problem_17&oldid=199619"