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
Contents
Problem
A subset of the integers 
has the property that none of its members is 3 times another. What is the largest number of members such a subset can have?
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 
Solution 2
Write down in a column the elements 
which are indivisible by three, and then follow each one by 
![\[\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}\]](http://latex.artofproblemsolving.com/1/2/6/1261b43b33557578b2ffd319b00ef4d01d697fb4.png)
We can take at most 
elements from the first row, and at most 
elements from each of the next seven rows. After that we can take only 
from any following row. Thus the answer is 
the number of integers between 
and 
inclusive which are indivisible by three.
There are 
multiples of three in that range, so there are 
non-multiples, and 
, which is
See also
| 1990 AHSME (Problems • Answer Key • Resources) | ||
| 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. 
