Difference between revisions of "1990 AHSME Problems/Problem 29"
(New page: ==Problem== Each of ten girls around a circle chooses a number and tells it to the neighbor on each side. Thus each person gives out one number and receives two numbers. Each girl then ann...) |
m (→Solution 1) |
||
(14 intermediate revisions by 9 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem== | + | == Problem == |
− | |||
− | + | A subset of the integers <math>1,2,\cdots,100</math> has the property that none of its members is 3 times another. What is the largest number of members such a subset can have? | |
− | {{ | + | <math>\text{(A) } 50\quad |
+ | \text{(B) } 66\quad | ||
+ | \text{(C) } 67\quad | ||
+ | \text{(D) } 76\quad | ||
+ | \text{(E) } 78</math> | ||
− | ==Solution== | + | == Solution 1 == |
− | + | Notice that inclusion of the integers from <math>34</math> to <math>100</math> is allowed as long as no integer between <math>11</math> and <math>33</math> inclusive is within the set. This provides a total of <math>100 - 34 + 1</math> = 67 solutions. | |
− | ==See also== | + | Further analyzation of the remaining integers between <math>1</math> and <math>10</math>, we notice that we can include all the numbers except <math>3</math> (as including <math>3</math> would force us to remove both <math>9</math> and <math>1</math>) to obtain the maximum number of <math>9</math> solutions. |
+ | |||
+ | Thus, <math>67 + 9 = 76</math>, yielding our answer, <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 == | ||
+ | {{AHSME box|year=1990|num-b=28|num-a=30}} | ||
+ | |||
+ | [[Category: Intermediate Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 19:25, 25 September 2020
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 from to
is allowed as long as no integer between
and
inclusive is within the set. This provides a total of
= 67 solutions.
Further analyzation of the remaining integers between and
, we notice that we can include all the numbers except
(as including
would force us to remove both
and
) to obtain the maximum number of
solutions.
Thus, , yielding our answer,
Solution 2
Write down in a column the elements which are indivisible by three, and then follow each one by
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 30 | |
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.