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 "1987 AIME Problems/Problem 3"

m (→‎See also)
m (→‎Solution 1)
 
(15 intermediate revisions by 11 users not shown)
Line 1: Line 1:
−
{{empty}}
 
 
== Problem ==
 
== Problem ==
 +
By a proper [[divisor]] of a [[natural number]] we mean a [[positive]] [[integer|integral]] divisor other than 1 and the number itself. A natural number greater than 1 will be called ''nice'' if it is equal to the product of its distinct proper divisors. What is the sum of the first ten nice numbers?
 +
 +
== Solution 1==
 +
Let <math>p(n)</math> denote the product of the distinct proper divisors of <math>n</math>. A number <math>n</math> is ''nice'' in one of two instances:
 +
#It has exactly two distinct [[prime]] divisors.
 +
#:If we let <math>n = pq</math>, where <math>p,q</math> are the prime factors, then its proper divisors are <math>p</math> and <math>q</math>, and <math>p(n) = p \cdot q = n</math>.
 +
#It is the cube of a prime number.
 +
#:If we let <math>n=p^3</math> with <math>p</math> prime, then its proper divisors are <math>p</math> and <math>p^2</math>, and <math>p(n) = p \cdot p^2 =n</math>.
 +
 +
We now show that the above are the only two cases. Suppose that another nice number existed that does not fall into one of these two categories. Then we can either express it in the form <math>n = pqr</math> (with <math>p,q</math> prime and <math>r > 1</math>) or <math>n = p^e</math> (with <math>e \neq 3</math>).
 +
In the former case, it suffices to note that <math>p(n) \ge (pr) \cdot (qr) = pqr^2 > pqr = n</math>.
 +
 +
In the latter case, then <math>p(n) = p \cdot p^2 \cdots p^{(e-1)} = p^{(e-1)e/2}</math>.
 +
 +
For <math>p(n) = n</math>, we need <math>p^{(e-1)e/2} = p^e \Longrightarrow e^2 - e = 2e \Longrightarrow </math> <math>e = 0</math> or <math>e = 3</math>. 
 +
 +
Since <math>e \neq 3</math>, in the case <math>e = 0 \Longrightarrow n = 1</math> does not work.
 +
 +
Thus, listing out the first ten numbers to fit this form, <math>2 \cdot 3 = 6,\ 2^3 = 8,\ 2 \cdot 5 = 10,</math> <math>\ 2 \cdot 7 = 14,\ 3 \cdot 5 = 15,\ 3 \cdot 7 = 21,</math> <math>\ 2 \cdot 11 = 22,\ 2 \cdot 13 = 26,</math> <math>\ 3^3 = 27,\ 3 \cdot 11 = 33</math>.
 +
[[Sum]]ming these yields <math>\boxed{182}</math>.
 +
 +
== Solution 2==
 +
Alternatively, we could note that <math>n</math> is only nice when it only has two proper divisors, which, when multiplied, clearly yield <math>n</math>. We know that when the [[prime factorization]] of <math>n = a_1^{b_1} \cdot a_2^{b_2} \cdot a_3^{b_3} . . . \cdot a_m^{b_m}</math>, the number of factors <math>f(n)</math> of <math>n</math> is <cmath>f(n) = (b_1 + 1)(b_2 +1)(b_3 +1) . . . (b_m +1).</cmath>
 +
 +
Since <math>n</math> is nice, it may only have <math>4</math> factors (<math>1</math>, <math>n</math>, <math>p</math>, and <math>q</math>). This means that <math>f(n) = 4</math>. The number <math>4</math> can only be factored into <math>(2)(2)</math> or <math>(4)(1)</math>, which means that either <math>b_1 = 1</math> and <math>b_2 = 1</math>, or <math>b_1 = 3</math>. Therefore the only two cases are <math>n = pq</math>, or <math>n = p^3</math>.
 +
And then continue.
  
−
== Solution ==
 
−
{{solution}}
 
 
== See also ==
 
== See also ==
−
* [[1987 AIME Problems]]
+
{{AIME box|year=1987|num-b=2|num-a=4}}
  
−
{{AIME box|year=1987|num-b=2|num-a=4}}
+
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 08:29, 9 January 2023

Problem

By a proper divisor of a natural number we mean a positive integral divisor other than 1 and the number itself. A natural number greater than 1 will be called nice if it is equal to the product of its distinct proper divisors. What is the sum of the first ten nice numbers?

Solution 1

Let $p(n)$ denote the product of the distinct proper divisors of $n$. A number $n$ is nice in one of two instances:

  1. It has exactly two distinct prime divisors.
    If we let $n = pq$, where $p,q$ are the prime factors, then its proper divisors are $p$ and $q$, and $p(n) = p \cdot q = n$.
  2. It is the cube of a prime number.
    If we let $n=p^3$ with $p$ prime, then its proper divisors are $p$ and $p^2$, and $p(n) = p \cdot p^2 =n$.

We now show that the above are the only two cases. Suppose that another nice number existed that does not fall into one of these two categories. Then we can either express it in the form $n = pqr$ (with $p,q$ prime and $r > 1$) or $n = p^e$ (with $e \neq 3$). In the former case, it suffices to note that $p(n) \ge (pr) \cdot (qr) = pqr^2 > pqr = n$.

In the latter case, then $p(n) = p \cdot p^2 \cdots p^{(e-1)} = p^{(e-1)e/2}$.

For $p(n) = n$, we need $p^{(e-1)e/2} = p^e \Longrightarrow e^2 - e = 2e \Longrightarrow$ $e = 0$ or $e = 3$.

Since $e \neq 3$, in the case $e = 0 \Longrightarrow n = 1$ does not work.

Thus, listing out the first ten numbers to fit this form, $2 \cdot 3 = 6,\ 2^3 = 8,\ 2 \cdot 5 = 10,$ $\ 2 \cdot 7 = 14,\ 3 \cdot 5 = 15,\ 3 \cdot 7 = 21,$ $\ 2 \cdot 11 = 22,\ 2 \cdot 13 = 26,$ $\ 3^3 = 27,\ 3 \cdot 11 = 33$. Summing these yields $\boxed{182}$.

Solution 2

Alternatively, we could note that $n$ is only nice when it only has two proper divisors, which, when multiplied, clearly yield $n$. We know that when the prime factorization of $n = a_1^{b_1} \cdot a_2^{b_2} \cdot a_3^{b_3} . . . \cdot a_m^{b_m}$, the number of factors $f(n)$ of $n$ is \[f(n) = (b_1 + 1)(b_2 +1)(b_3 +1) . . . (b_m +1).\]

Since $n$ is nice, it may only have $4$ factors ($1$, $n$, $p$, and $q$). This means that $f(n) = 4$. The number $4$ can only be factored into $(2)(2)$ or $(4)(1)$, which means that either $b_1 = 1$ and $b_2 = 1$, or $b_1 = 3$. Therefore the only two cases are $n = pq$, or $n = p^3$. And then continue.

See also

1987 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME 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=1987_AIME_Problems/Problem_3&oldid=186131"