AoPSWiki
Want to learn how to tackle those tough MATHCOUNTS and AMC counting and probability problems? Check out Art of Problem Solving's Introduction to Counting & Probability by David Patrick.

2004 IMO Shortlist Problems/N1

From AoPSWiki

Contents

Problem

(Belarus) Let \displaystyle \tau(n) denote the number of positive divisors of the positive integer \displaystyle n. Prove that there exist infinitely many positive integers \displaystyle a such that the equation

\displaystyle \tau(an) = n

does not have a positive solution \displaystyle n.

This was also a problem on the 2005 TSTs for Australia and Germany.

Solutions

Solution 1

If \displaystyle \tau(an) = n, then \frac{an}{\tau(an)} = a, i.e., there exists \displaystyle m such that \frac{m}{\tau(m)} = a. The converse is also true, since \displaystyle \tau(m)a = m (i.e., a \mid m.) Thus the existance of \displaystyle n such that \displaystyle \tau(an) = n is equivalent to the existance of \displaystyle m such that \displaystyle \frac{m}{\tau(m)} = a.

Note that for any integer \displaystyle m has at most \sqrt{m} divisors less than or equal to \sqrt{m}, and for each divisor d > \sqrt{n}, a divisor \frac{n}{d} < \sqrt{n}. Hence we obtain the inequality

{}\tau(n) \le 2\sqrt{n} \qquad (*).

It is sufficient to prove that for prime \displaystyle p \ge 5, the equation \frac{m}{\tau(m)} = p^{p-1} has no solutions. Assume the contrary. Clearly, if \displaystyle m is a solution, then p^{p-1} \mid m, so let \displaystyle m = p^k \cdot c, where \displaystyle c is not divisible by \displaystyle p. We have

{}\frac{p^k c}{(k+1)\tau(c)} = p^{p-1} \qquad (**).

We must clearly have k \ge p-1. If \displaystyle k = p-1, then \frac{c}{\tau(c)} must be divisible by \displaystyle p, a contradiction, since p \nmid c. On the other hand, if \displaystyle k = p, then by \displaystyle (**) we have \displaystyle pc = (p+1)\tau(c). This implies p \mid \tau(c), so p \le \tau(c) \le 2\sqrt{c}. But by \displaystyle (*), we have

\sqrt{c} = \frac{c}{\sqrt{c}} \le \frac{2c}{\tau(c)} = 2p^{p-1} \cdot \frac{p+1}{p^p} = \frac{2(p+1)}{p}.

This implies p \le 2 \sqrt{c} \le \frac{4(p+1)}{p}, a contradiction for p \ge 5.

Thus we must have k \ge p+1. Here, we have

\frac{p^{p-1} (k+1)}{p^k} = \frac{s}{\tau(s)} \ge \frac{s}{2\sqrt{s}} = \frac{\sqrt{s}}{2}.

But by induction, we have \frac{k+1}{p^{k-p+1}} < \frac{1}{2}, which implies \displaystyle s < 1, a final contradiction.

Solution 2

As in the first solution, it is sufficient to show that there are infinitely many \displaystyle a such that \frac{m}{\tau(m)} = a has no solutions.

We note that for prime \displaystyle p, \frac{p^k}{\tau(p^k)} = \frac{p^k}{k+1} is a non-decreasing function of \displaystyle k, for \frac{\frac{p^{k+1}}{k+2}}{\frac{p^k}{k+1}} = \frac{p(k+1)}{k+2} \ge 1. We also note that since there are only \displaystyle m positive integers less than or equal to \displaystyle m, {} \frac{m}{\tau(m)} \ge 1. We also note that \displaystyle \tau is a weak multiplicative function, so for relatively prime \displaystyle m,n, \frac{mn}{\tau(mn)} = \frac{m}{\tau(m)} \cdot \frac{n}{\tau(n)}.

Now, suppose that there exists some integer \displaystyle a_0 such that for all integers \displaystyle m, \frac{m}{\tau(m)} \neq a_0. Let \displaystyle p be any prime greater than \displaystyle a_0+1. We claim that there is no integer \displaystyle m such that \frac{m}{\tau(m)} = p^{a_0-1}. Suppose the contrary. Clearly, we must have p^{a_0-1} \mid m, so let m = p^k\cdot c, for some \displaystyle c not divisible by \displaystyle p. If \displaystyle k is less than \displaystyle a_0-1, then the numerator of \frac{m}{\tau(m)} is not divisible by p^{a_0-1}, a contradiction. If \displaystyle k = a_0 -1, then we must have p^{a_0-1} = \frac{p^{a_0-1}}{a_0} \cdot \frac{c}{\tau(c)}, which implies \frac{c}{\tau(c)} = a_0, a contradiction. So \displaystyle k > a_0-1. But then we have

\frac{m}{\tau(m)} \ge \frac{p^{k}}{k+1} \ge \frac{p^{a_0}}{a_0+1} > p^{a_0-1},

a contradiction. Thus it is sufficient to prove the existance of one \displaystyle a_0 such that \displaystyle \tau(a_0n) = n has no solution \displaystyle n.

We will now prove that these is no integer \displaystyle m such that \frac{m}{\tau(m)} = \frac{6}{5}. Suppose that there is such an integer m. Since 5 \mid \tau(m) and \tau \left( \prod_{i=1}^{n}p_i^{e_i} \right) = \prod_{i=1}^n (e_i+1) for distinct primes \displaystyle p_i, it follows that \displaystyle m must be divisible by \displaystyle p^4, for some prime \displaystyle p. But then we have

\frac{m}{\tau(m)} \ge \frac{p^4}{5} \ge \frac{2^4}{5} > \frac{6}{5},

a contadiction.

We will now prove that for no integer \displaystyle m does the equation \frac{m}{\tau(m)} = 5^4 hold. Suppose on the contrary that there exists such an \displaystyle m. We must have m = 5^{k}\cdot c, for some \displaystyle c not divisible by 5. We must clearly have k \ge 4. In fact, we must have \displaystyle k > 4, for \displaystyle k=4 gives us {} \frac{m}{\tau(m)} = \frac{5^4}{4+1} \cdot \frac{c}{\tau(c)} = 5^3 \cdot \frac{c}{\tau(c)}, which cannot be divisible by \displaystyle 5^4. We cannot have \displaystyle k = 5, either, since we then have \frac{m}{\tau(m)} = \frac{5^5}{6} \cdot \frac{c}{\tau(c)}, which gives us \frac{c}{\tau(c)} = \frac{6}{5}. Then

\frac{m}{\tau(m)} \ge \frac{5^k}{k+1} \ge \frac{5^6}{7} > 5^4,

a contradiction. Thus \displaystyle m does not exist and the problem is solved.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/2004_IMO_Shortlist_Problems/N1"
Looking for a challenging geometry text? Preparing for MATHCOUNTS or the AMC exams? Check out Art of Problem Solving's Introduction to Geometry by Richard Rusczyk.
© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us