Mathematical Food for Thought

  
 
 

  • About

    Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.
  
A Square of Divisors. Topic: Number Theory. Level: AIME/Olympiad. May 8th, 2007

Problem: (1999 Canada – #3) Determine all positive integers n > 1 with the property that n = (d(n))^2. Here d(n) denotes the number of positive divisors of n.

Solution: So, testing some small numbers yields n = 9 as a solution. We claim that this is the only such solution.

Clearly, since n is a square, we can use a variant of the usual prime decomposition and say that n = p_1^{2e_1} p_2^{2e_2} \cdots p_k^{2e_k} .

Furthermore, again since n is a square, we know

d(n) = (2e_1+1)(2e_2+1) \cdots (2e_k+1)

is odd, so n = (d(n))^2 must be odd as well, i.e. 2 is not one of the p_i . Then we use the equation given to us to get

p_1^{2e_1} p_2^{2e_2} \cdots p_k^{2e_k} = (2e_1+1)^2(2e_2+1)^2 \cdots (2e_k+1)^2

p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} = (2e_1+1)(2e_2+1) \cdots (2e_k+1) .

Note, however, that by Bernoulli’s Inequality (overkill, I know) we have for i = 1, 2, \ldots, k

(1+(p_i-1))^{e_i} \ge 1+(p_i-1)e_i \ge 2e_i+1

with equality iff p_i = 3 and e_i = 1 . So

p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \ge (2e_1+1)(2e_2+1) \cdots (2e_k+1) .

Since we want equality, we must have p_i = 3 and e_i = 1 for all i . But since the primes are supposed to be distinct we can have exactly one prime so that n = 3^2 = 9 is the only solution. QED.

——————–

Comment: Another one of those problems that you kind of look at the result and you’re like huh, that’s interesting. But anyway, just throwing in some weak inequalities led to a pretty straightforward solution. As long as you know how to find the number of divisors of a positive integer it isn’t too much of a stretch to figure the rest out, though it make take some time to get in the right direction since the problem is quite open-ended.

——————–

Practice Problem: (1999 Canada – #4) Suppose a_1,a_2,\cdots,a_8 are eight distinct integers from \{1,2,\ldots,16,17\}. Show that there is an integer k > 0 such that the equation a_i – a_j = k has at least three different solutions. Also, find a specific set of 7 distinct integers from \{1,2,\ldots,16,17\} such that the equation a_i – a_j = k does not have three distinct solutions for any k > 0.

Posted in AIME, Number Theory, Olympiad || 6 Comments »

6 Responses to “A Square of Divisors. Topic: Number Theory. Level: AIME/Olympiad.”

  1. Xuan Says:
    May 9th, 2007 at 7:03 pm

    This actually has nothing to do with your question, but i thought it was pretty interesting:

    Isn’t nonexistence or existence only as an idea still a form of existence?

    Which analogy is better?:

    existence:nonexistence
    1 : -1

    existence:nonexistence
    1 : 0

  2. paladin8 Says:
    May 9th, 2007 at 8:53 pm

    1 : 0.

    Nonexistence is the absence of existence. And yes, the concept of nonexistence is a form of existence, but who claimed otherwise? Nonexistence does not have to describe itself.

  3. blue_giraffe Says:
    May 9th, 2007 at 10:46 pm

    ….

  4. paladin8 Says:
    May 10th, 2007 at 6:27 am

    Hey! You should’ve gone to bed.

  5. Evan Says:
    May 22nd, 2007 at 8:35 pm

    Looking at this, it appears obvious that n = 1 is also a solution

  6. paladin8 Says:
    May 22nd, 2007 at 8:38 pm

    Good call. Oh well.

Leave a Reply

You must be logged in to post a comment.
Google

 

  
 
free web counters
Etronics