Maths Olympiad Prep

Library / /8 of 8

Number theory Difficulty 5.7 AIME, harder Prove it Brazil

Let d(n)d(n) be the number of positive divisors of nn. Show that
n(12+13++1n)d(1)+d(2)++d(n)n(1+12+13++1n) n\left(\frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}\right) \le d(1) + d(2) + \dots + d(n) \le n\left(1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}\right)

Solution

Let's count the number NN of pairs (j,k)(j, k) such that jj divides kk and 1j,kn1 \le j, k \le n. Fixing jj, we must count the multiples of jj, which is nj\lfloor \frac{n}{j} \rfloor. So
N=n1+n2+n3++nn N = \lfloor \frac{n}{1} \rfloor + \lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{3} \rfloor + \dots + \lfloor \frac{n}{n} \rfloor
Fixing kk, we must count the number of divisors of kk, which is d(k)d(k) and then N=d(1)+d(2)++d(n)N = d(1) + d(2) + \dots + d(n). So
d(1)+d(2)++d(n)=n1+n2+n3++nn d(1) + d(2) + \dots + d(n) = \lfloor \frac{n}{1} \rfloor + \lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{3} \rfloor + \dots + \lfloor \frac{n}{n} \rfloor
and since x1<xxx - 1 < \lfloor x \rfloor \le x
(n11)+(n21)++(nn1)<d(1)+d(2)++d(n)n1+n2++nn \left(\frac{n}{1} - 1\right) + \left(\frac{n}{2} - 1\right) + \dots + \left(\frac{n}{n} - 1\right) < d(1) + d(2) + \dots + d(n) \le \frac{n}{1} + \frac{n}{2} + \dots + \frac{n}{n}
n(12+13++1n)d(1)+d(2)++d(n)n(1+12+13++1n) n \left( \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right) \le d(1) + d(2) + \dots + d(n) \le n \left( 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right)

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.