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 "1990 AHSME Problems/Problem 29"

m (→‎Solution 1)
m (→‎Solution 1)
 
(5 intermediate revisions by 3 users not shown)
Line 10: Line 10:
  
 
== Solution 1 ==
 
== Solution 1 ==
−
Notice that inclusion of the integers between <math>34</math> to <math>100</math> inclusive 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<math> solutions.  
+
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.  
  
−
Further analyzing 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.  
+
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}$
+
Thus, <math>67 + 9 = 76</math>, yielding our answer, <math>\fbox{D}</math>
  
 
== Solution 2 ==
 
== Solution 2 ==
Line 24: Line 24:
 
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>
 
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=30}}   
  
 
[[Category: Intermediate Number Theory Problems]]
 
[[Category: Intermediate Number Theory Problems]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 18:25, 25 September 2020

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 from $34$ to $100$ 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 analyzation of 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$, yielding our answer, $\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 (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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1990_AHSME_Problems/Problem_29&oldid=134067"