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 "1996 AHSME Problems/Problem 29"
 
(14 intermediate revisions by 7 users not shown)
Line 4: Line 4:
  
 
<math> \text{(A)}\ 32\qquad\text{(B)}\ 34\qquad\text{(C)}\ 35\qquad\text{(D)}\ 36\qquad\text{(E)}\ 38 </math>
 
<math> \text{(A)}\ 32\qquad\text{(B)}\ 34\qquad\text{(C)}\ 35\qquad\text{(D)}\ 36\qquad\text{(E)}\ 38 </math>
 +
 +
==Solution 1==
 +
 +
Working with the second part of the problem first, we know that <math>3n</math> has <math>30</math> divisors.  We try to find the various possible prime factorizations of <math>3n</math> by splitting <math>30</math> into various products of <math>1, 2</math> or <math>3</math> integers.
 +
 +
<math>30 \rightarrow p^{29}</math>
 +
 +
<math>2 \cdot 15 \rightarrow pq^{14}</math>
 +
 +
<math>3\cdot 10 \rightarrow p^2q^9</math>
 +
 +
<math>5\cdot 6 \rightarrow p^4q^5</math>
 +
 +
<math>2\cdot 3\cdot 5 \rightarrow pq^2r^4</math>
 +
 +
The variables <math>p, q, r</math> are different prime factors, and one of them must be <math>3</math>.  We now try to count the factors of <math>2n</math>, to see which prime factorization is correct and has <math>28</math> factors.
 +
 +
In the first case, <math>p=3</math> is the only possibility.  This gives <math>2n = 2\cdot p^{28}</math>, which has <math>2\cdot {29}</math> factors, which is way too many.
 +
 +
In the second case, <math>p=3</math> gives <math>2n = 2q^{14}</math>.  If <math>q=2</math>, then there are <math>16</math> factors, while if <math>q\neq 2</math>, there are <math>2\cdot 15 = 30</math> factors.
 +
 +
In the second case, <math>q=3</math> gives <math>2n = 2p3^{13}</math>.  If <math>p=2</math>, then there are <math>3\cdot 13</math> factors, while if <math>p\neq 2</math>, there are <math>2\cdot 2 \cdot 13</math> factors.
 +
 +
In the third case, <math>p=3</math> gives <math>2n = 2\cdot 3\cdot q^9</math>.  If <math>q=2</math>, then there are <math>11\cdot 2 = 22</math> factors, while if <math>q \neq 2</math>, there are <math>2\cdot 2\cdot 10</math> factors.
 +
 +
In the third case, <math>q=3</math> gives <math>2n = 2\cdot p^2\cdot 3^8</math>.  If <math>p=2</math>, then there are <math>4\cdot 9</math> factors, while if <math>p \neq 2</math>, there are <math>2\cdot 3\cdot 9</math> factors.
 +
 +
In the fourth case, <math>p=3</math> gives <math>2n = 2\cdot 3^3\cdot q^5</math>.  If <math>q=2</math>, then there are <math>7\cdot 4= 28</math> factors.  This is the factorization we want.
 +
 +
Thus, <math>3n = 3^4 \cdot 2^5</math>, which has <math>5\cdot 6 = 30</math> factors, and <math>2n = 3^3 \cdot 2^6</math>, which has <math>4\cdot 7 = 28</math> factors.
 +
 +
In this case, <math>6n = 3^4\cdot 2^6</math>, which has <math>5\cdot 7 = 35</math> factors, and the answer is <math>\boxed{C}</math>
 +
 +
 +
== Solution 2 ==
 +
Because <math>2n</math> has <math>28</math> factors and <math>3n</math> has <math>30</math> factors, we should rewrite the number <math>n = 2^{e_1}3^{e_2}... p_n^{e_n}</math>
 +
As the formula for the number of divisors for such a number gives:
 +
<math>(e_1+1)(e_2+1)... (e_n+1)</math>
 +
We plug in the variations we need to make for the cases <math>2n</math> and <math>3n</math>.
 +
<math>2n</math> has <math>(e_1+2)(e_2+1)(e_3+1)... (e_n+1) = 28</math>
 +
<math>3n</math> has <math>(e_1+1)(e_2+2)(e_3+1)...(e_n+1) = 30</math>
 +
 +
If we take the  top and divide by the bottom, we get the following equation:
 +
<math>\frac{(e_1+2)(e_2+1)}{(e_1+1)(e_2+2)} = \frac{14}{15}</math>. Letting <math>e_1=x</math> and <math>e_2 = y</math> for convenience and expanding this out gives us:
 +
<math>xy-13x+16y+2=0</math>
 +
 +
We can use Simon's Favorite Factoring Trick (SFFT) to turn this back into:
 +
<math>(x+16)(y-13) +2 + 208 = 0</math> or
 +
<math>(x+16)(y-13) = - 210</math>
 +
 +
As we want to be dealing with rather reasonable numbers for <math>x</math> and <math>y</math>, we try to make the <math>x+16</math> term the slightly larger term and the <math>y-13</math> term the slightly smaller term. This effect is achieved when <math>x+16 = 21</math> and <math>y-13 = -10</math>. Therefore, <math>x = 5, y = 3</math>. We get that this already satisfies the requirements for the number we are looking for, and we take <math>(5+2)(3+2) = \boxed{35}</math>
 +
 +
==Solution 3 (Alcumus Solution)==
 +
Let <math>\, 2^{e_1} 3^{e_2} 5^{e_3} \cdots \,</math> be the prime factorization of <math>\, n</math>. Then the number of positive divisors of <math>\, n \,</math> is <math>\, (e_1 + 1)(e_2 + 1)(e_3 + 1) \cdots \; </math>. In view of the given information, we have <cmath> 28 = (e_1 + 2)(e_2 + 1)P </cmath>and <cmath> 30 = (e_1 + 1)(e_2 + 2)P, </cmath>where <math>\, P = (e_3 + 1)(e_4 + 1) \cdots \; </math>. Subtracting the first equation from the second, we obtain <math>\, 2 = (e_1 - e_2)P, \,</math> so either <math>\, e_1 - e_2 = 1 \,</math> and <math>\, P = 2, \,</math> or <math>\, e_1 - e_2 = 2 \,</math> and <math>\, P = 1</math>. The first case yields <math>\, 14 = (e_1 + 2)e_1 \,</math> and <math>\, (e_1 + 1)^2 = 15</math>; since <math>\, e_1 \,</math> is a nonnegative integer, this is impossible. In the second case, <math>\, e_2 = e_1 - 2 \,</math> and <math>\, 30 = (e_1 + 1)e_1, \,</math> from which we find <math>\, e_1 = 5 \,</math> and <math>\, e_2 = 3</math>. Thus <math>\, n = 2^5 3^3, \,</math> so <math>\, 6n = 2^6 3^4 \,</math> has <math>\, (6+1)(4+1) = \boxed{35} \,</math> positive divisors.
  
 
==See also==
 
==See also==
 
{{AHSME box|year=1996|num-b=28|num-a=30}}
 
{{AHSME box|year=1996|num-b=28|num-a=30}}
 +
{{MAA Notice}}

Latest revision as of 04:52, 26 October 2023

Problem

If $n$ is a positive integer such that $2n$ has $28$ positive divisors and $3n$ has $30$ positive divisors, then how many positive divisors does $6n$ have?

$\text{(A)}\ 32\qquad\text{(B)}\ 34\qquad\text{(C)}\ 35\qquad\text{(D)}\ 36\qquad\text{(E)}\ 38$

Solution 1

Working with the second part of the problem first, we know that $3n$ has $30$ divisors. We try to find the various possible prime factorizations of $3n$ by splitting $30$ into various products of $1, 2$ or $3$ integers.

$30 \rightarrow p^{29}$

$2 \cdot 15 \rightarrow pq^{14}$

$3\cdot 10 \rightarrow p^2q^9$

$5\cdot 6 \rightarrow p^4q^5$

$2\cdot 3\cdot 5 \rightarrow pq^2r^4$

The variables $p, q, r$ are different prime factors, and one of them must be $3$. We now try to count the factors of $2n$, to see which prime factorization is correct and has $28$ factors.

In the first case, $p=3$ is the only possibility. This gives $2n = 2\cdot p^{28}$, which has $2\cdot {29}$ factors, which is way too many.

In the second case, $p=3$ gives $2n = 2q^{14}$. If $q=2$, then there are $16$ factors, while if $q\neq 2$, there are $2\cdot 15 = 30$ factors.

In the second case, $q=3$ gives $2n = 2p3^{13}$. If $p=2$, then there are $3\cdot 13$ factors, while if $p\neq 2$, there are $2\cdot 2 \cdot 13$ factors.

In the third case, $p=3$ gives $2n = 2\cdot 3\cdot q^9$. If $q=2$, then there are $11\cdot 2 = 22$ factors, while if $q \neq 2$, there are $2\cdot 2\cdot 10$ factors.

In the third case, $q=3$ gives $2n = 2\cdot p^2\cdot 3^8$. If $p=2$, then there are $4\cdot 9$ factors, while if $p \neq 2$, there are $2\cdot 3\cdot 9$ factors.

In the fourth case, $p=3$ gives $2n = 2\cdot 3^3\cdot q^5$. If $q=2$, then there are $7\cdot 4= 28$ factors. This is the factorization we want.

Thus, $3n = 3^4 \cdot 2^5$, which has $5\cdot 6 = 30$ factors, and $2n = 3^3 \cdot 2^6$, which has $4\cdot 7 = 28$ factors.

In this case, $6n = 3^4\cdot 2^6$, which has $5\cdot 7 = 35$ factors, and the answer is $\boxed{C}$


Solution 2

Because $2n$ has $28$ factors and $3n$ has $30$ factors, we should rewrite the number $n = 2^{e_1}3^{e_2}... p_n^{e_n}$ As the formula for the number of divisors for such a number gives: $(e_1+1)(e_2+1)... (e_n+1)$ We plug in the variations we need to make for the cases $2n$ and $3n$. $2n$ has $(e_1+2)(e_2+1)(e_3+1)... (e_n+1) = 28$ $3n$ has $(e_1+1)(e_2+2)(e_3+1)...(e_n+1) = 30$

If we take the top and divide by the bottom, we get the following equation: $\frac{(e_1+2)(e_2+1)}{(e_1+1)(e_2+2)} = \frac{14}{15}$. Letting $e_1=x$ and $e_2 = y$ for convenience and expanding this out gives us: $xy-13x+16y+2=0$

We can use Simon's Favorite Factoring Trick (SFFT) to turn this back into: $(x+16)(y-13) +2 + 208 = 0$ or $(x+16)(y-13) = - 210$

As we want to be dealing with rather reasonable numbers for $x$ and $y$, we try to make the $x+16$ term the slightly larger term and the $y-13$ term the slightly smaller term. This effect is achieved when $x+16 = 21$ and $y-13 = -10$. Therefore, $x = 5, y = 3$. We get that this already satisfies the requirements for the number we are looking for, and we take $(5+2)(3+2) = \boxed{35}$

Solution 3 (Alcumus Solution)

Let $\, 2^{e_1} 3^{e_2} 5^{e_3} \cdots \,$ be the prime factorization of $\, n$. Then the number of positive divisors of $\, n \,$ is $\, (e_1 + 1)(e_2 + 1)(e_3 + 1) \cdots \;$. In view of the given information, we have \[28 = (e_1 + 2)(e_2 + 1)P\]and \[30 = (e_1 + 1)(e_2 + 2)P,\]where $\, P = (e_3 + 1)(e_4 + 1) \cdots \;$. Subtracting the first equation from the second, we obtain $\, 2 = (e_1 - e_2)P, \,$ so either $\, e_1 - e_2 = 1 \,$ and $\, P = 2, \,$ or $\, e_1 - e_2 = 2 \,$ and $\, P = 1$. The first case yields $\, 14 = (e_1 + 2)e_1 \,$ and $\, (e_1 + 1)^2 = 15$; since $\, e_1 \,$ is a nonnegative integer, this is impossible. In the second case, $\, e_2 = e_1 - 2 \,$ and $\, 30 = (e_1 + 1)e_1, \,$ from which we find $\, e_1 = 5 \,$ and $\, e_2 = 3$. Thus $\, n = 2^5 3^3, \,$ so $\, 6n = 2^6 3^4 \,$ has $\, (6+1)(4+1) = \boxed{35} \,$ positive divisors.

See also

1996 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=1996_AHSME_Problems/Problem_29&oldid=200243"