Saturday, June 17, 2006

Egyptian. Topic: Number Theory. Level: AIME.

Problem: (1991 India National Olympiad - #10) For any positive integer $n$, let $s(n)$ denote the number of ordered pairs $(x,y)$ of positive integers for which $\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$. Determine the set of positive integers for which $s(n) = 5$.

Solution: Rewrite the equation as

$ n(x+y) = xy $

$ (x-n)(y-n) = n^2 $.

So for each pair $ (a,b) $ with $ ab = n^2 $, there exist a pair $ (x,y) = (a+n, b+n) $ satisfying

$ \frac{1}{x}+\frac{1}{y} = \frac{1}{n} $.

Hence we want to find an $ n^2 $ with $ 5 $ distinct factors. We see that $ n^2 = p^4 $ for $ p $ prime is the only case (since $ 5 $ itself is prime, meaning $ n = p^rq^s $ is not possible), so we thus have $ s(n) = 5 $ for $ n = p^2 $, where $ p $ is any prime. QED.

--------------------

Comment: A standard problem involving Simon's Favorite Factoring Trick and counting the number of divisors. SFFT is always something to look for when you have $ xy, x, y $ terms (sorta like completing the square except not).

--------------------

Practice Problem: (1991 India National Olympiad - #1) Find the number of positive integers $n$ for which

(i) $n \leq 1991$;

(ii) $6$ is a factor of $(n^2 + 3n +2)$.

2 comments:

  1. n^2+3n+2 factors as (n+1)(n+2)

    For all odd values of n, (n+1) is even and so contains 2 as a factor. So we want either odd values of n that are 2 less than a multiple of 3, or one less than a multiple of 6. There are 663 multiples of 3 less than 1991, 332 of which are odd - each one has a corresponding n value. There are 331 multiples of 6 - each one also has a corresponding n value, so a total of 663 odd values of n that work.

    For even numbers, there are 331 values of n that result in (n+2) containing a factor of 6, and 332 values that make (n+1) contain a factor of 3.

    Total number of possible values for n is then 1326 ... I think

    ReplyDelete
  2. n^2 + 3n + 2 is always even, so we only want to concern ourselves with divisibility b 3. We have it for n \equiv 1, 2 \bmod 3, and for each case we have 663 possibilities, for a total of 1326.

    ReplyDelete