Difference between revisions of "1990 AHSME Problems/Problem 29"

(Solution)
Line 9: Line 9:
 
\text{(E) } 78</math>
 
\text{(E) } 78</math>
  
== Solution ==
+
== Solution 1 ==
 
Notice that inclusion of the integers between 34 to 100 inclusive is allowed as long as no integer between 11 and 33 inclusive is within the set. This provides a total of 100 - 34 + 1 = 67 solutions.  
 
Notice that inclusion of the integers between 34 to 100 inclusive is allowed as long as no integer between 11 and 33 inclusive is within the set. This provides a total of 100 - 34 + 1 = 67 solutions.  
  
Line 16: Line 16:
 
Thus, 67 + 9 = 76 <math>\fbox{D}</math>
 
Thus, 67 + 9 = 76 <math>\fbox{D}</math>
  
 +
== Solution 2 ==
 +
Write down in a column the elements <math>x</math> which are indivisible by three, and then follow each one by <math>3x, 9x, 27x, \ldots</math>
 +
 +
<cmath>\begin{array}{ccccc}1&3&9&27&81\\2&6&18&54\\4&12&36\\5&15&45\\7&21&63\\8&24&72\\10&30&90\\11&33&99\\13&39\\\vdots&\vdots\end{array}</cmath>
 +
We can take at most <math>3</math> elements from the first row, and at most <math>2</math> elements from each of the next seven rows. After that we can take only <math>1</math> from any following row. Thus the answer is <math>3+7\cdot 2\,+</math> the number of integers between <math>13</math> and <math>100</math> inclusive which are indivisible by three.
 +
 +
There are <math>\tfrac13(99-12)=29</math> multiples of three in that range, so there are <math>88-29=59</math> non-multiples, and <math>3+14+59=76</math>, which is <math>\fbox{D}</math>
 
== See also ==
 
== See also ==
 
{{AHSME box|year=1990|num-b=28|num-a=29}}   
 
{{AHSME box|year=1990|num-b=28|num-a=29}}   

Revision as of 22:50, 4 February 2016

Problem

A subset of the integers $1,2,\cdots,100$ has the property that none of its members is 3 times another. What is the largest number of members such a subset can have?

$\text{(A) } 50\quad \text{(B) } 66\quad \text{(C) } 67\quad \text{(D) } 76\quad \text{(E) } 78$

Solution 1

Notice that inclusion of the integers between 34 to 100 inclusive is allowed as long as no integer between 11 and 33 inclusive is within the set. This provides a total of 100 - 34 + 1 = 67 solutions.

Further analyzing the remaining integers between 1 and 10, we notice that we can include all the numbers except 3 (as including 3 would force us to remove both 9 and 1) to obtain the maximum number of 9 solutions.

Thus, 67 + 9 = 76 $\fbox{D}$

Solution 2

Write down in a column the elements $x$ which are indivisible by three, and then follow each one by $3x, 9x, 27x, \ldots$

\[\begin{array}{ccccc}1&3&9&27&81\\2&6&18&54\\4&12&36\\5&15&45\\7&21&63\\8&24&72\\10&30&90\\11&33&99\\13&39\\\vdots&\vdots\end{array}\] We can take at most $3$ elements from the first row, and at most $2$ elements from each of the next seven rows. After that we can take only $1$ from any following row. Thus the answer is $3+7\cdot 2\,+$ the number of integers between $13$ and $100$ inclusive which are indivisible by three.

There are $\tfrac13(99-12)=29$ multiples of three in that range, so there are $88-29=59$ non-multiples, and $3+14+59=76$, which is $\fbox{D}$

See also

1990 AHSME (ProblemsAnswer KeyResources)
Preceded by
Problem 28
Followed by
Problem 29
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 26 27 28 29 30
All AHSME Problems and Solutions

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

Invalid username
Login to AoPS