Maths Olympiad Prep

Library / /44 of 44

Number theory Difficulty 7.2 National Olympiad, round 2 Prove it Slovenia

For a positive integer n2n \ge 2 let τ(n)\tau(n) denote the number of positive divisors of nn, and let σ(n)\sigma(n) be the sum of these divisors. Prove that
n+12σ(n)τ(n)322n. \frac{n+1}{2} \ge \frac{\sigma(n)}{\tau(n)} \ge \frac{3}{2\sqrt{2}}\sqrt{n}.
For each of these inequalities also determine when the equality holds.

Solution

First consider the right inequality. Let n=p1k1p2k2psksn = p_1^{k_1} p_2^{k_2} \cdots p_s^{k_s}, (where p1,,psp_1, \dots, p_s are distinct primes and k1,,ksk_1, \dots, k_s are positive integers). Then
τ(n)=(k1+1)(k2+1)(ks+1) \tau(n) = (k_1 + 1)(k_2 + 1) \cdots (k_s + 1)
σ(n)=(1+p1++p1k1)(1+p2++p2k2)(1+ps++psks)=σ(p1k1psks). \begin{align*} \sigma(n) &= \left(1 + p_1 + \cdots + p_1^{k_1}\right) \left(1 + p_2 + \cdots + p_2^{k_2}\right) \cdots \left(1 + p_s + \cdots + p_s^{k_s}\right) \\ &= \sigma(p_1^{k_1} \cdots p_s^{k_s}). \end{align*}
So
σ(n)τ(n)n=1+p1++p1k1(k1+1)p1k121+p2++p2k2(k2+1)p2k221+ps++psks(ks+1)psks2. \frac{\sigma(n)}{\tau(n)\sqrt{n}} = \frac{1+p_1+\cdots+p_1^{k_1}}{(k_1+1)p_1^{\frac{k_1}{2}}} \cdot \frac{1+p_2+\cdots+p_2^{k_2}}{(k_2+1)p_2^{\frac{k_2}{2}}} \cdots \frac{1+p_s+\cdots+p_s^{k_s}}{(k_s+1)p_s^{\frac{k_s}{2}}}.
The factors in this product are independent, so it suffices to show that each one is bounded from below by 322\frac{3}{2\sqrt{2}}. We would like to prove that
1+p++pk(k+1)pk2322 \frac{1 + p + \cdots + p^k}{(k + 1) p^{\frac{k}{2}}} \geq \frac{3}{2\sqrt{2}}
for all p2p \ge 2 and k1k \ge 1 (the left-hand side is the smallest when p=2,k=1p = 2, k = 1).
Let x=px = \sqrt{p}. For every positive integer kk the function
fk(x)=1+x2+x4++x2kxk f_k(x) = \frac{1 + x^2 + x^4 + \dots + x^{2k}}{x^k}
is increasing when x>1x > 1.
When k=1k = 1 and x>y>1x > y > 1 we have
f1(x)f1(y)=(xy)+yxxy=(xy)(11xy)>0. f_1(x) - f_1(y) = (x - y) + \frac{y - x}{xy} = (x - y)\left(1 - \frac{1}{xy}\right) > 0.
In general
f2l(x)=1+f1(x2)++f1(x2l),(8) f_{2l}(x) = 1 + f_1(x^2) + \cdots + f_1(x^{2l}), \quad (8)
f2l+1(x)=f1(x3)++f1(x2l+1).(9) f_{2l+1}(x) = f_1(x^3) + \cdots + f_1(x^{2l+1}). \tag{9}
The functions f2l(x)f_{2l}(x) and f2l+1(x)f_{2l+1}(x) are obviously increasing. So, fk(x)f_k(x) is increasing in xx.
1+p+p2++pkpk21+2++2k2k21+p+p2++pk(k+1)pk21+2++2k(k+1)2k2 \begin{align*} \Rightarrow \frac{1+p+p^2+\cdots+p^k}{p^{\frac{k}{2}}} &\ge \frac{1+2+\cdots+2^k}{2^{\frac{k}{2}}} \\ \Rightarrow \frac{1+p+p^2+\cdots+p^k}{(k+1)p^{\frac{k}{2}}} &\ge \frac{1+2+\cdots+2^k}{(k+1)2^{\frac{k}{2}}} \end{align*}
Define g(k)=1+2++2k(k+1)2k2g(k) = \frac{1+2+\cdots+2^k}{(k+1)2^{\frac{k}{2}}}, kNk \in \mathbb{N}. Let us show that g(k)g(k) is increasing.
g(k+1)g(k)=1+2(1+2++2k)(k+2)2k221+2++2k(k+1)2k2=(k+1)+(1+2++2k)(2k+22k22)(k+1)(k+2)2k22>0 \begin{align*} g(k+1) - g(k) &= \frac{1 + 2(1 + 2 + \cdots + 2^k)}{(k+2)2^{\frac{k}{2}}\sqrt{2}} - \frac{1 + 2 + \cdots + 2^k}{(k+1)2^{\frac{k}{2}}} \\ &= \frac{(k+1) + (1 + 2 + \cdots + 2^k)(2k + 2 - \sqrt{2}k - 2\sqrt{2})}{(k+1)(k+2)2^{\frac{k}{2}}\sqrt{2}} > 0 \end{align*}
So,
1+p+p2++pk(k+1)pk21+2++2k(k+1)2k2322 \frac{1+p+p^2+\dots+p^k}{(k+1)p^{\frac{k}{2}}} \ge \frac{1+2+\dots+2^k}{(k+1)2^{\frac{k}{2}}} \ge \frac{3}{2\sqrt{2}}
We conclude that
σ(n)τ(n)n(322)s322 \frac{\sigma(n)}{\tau(n)\sqrt{n}} \ge \left( \frac{3}{2\sqrt{2}} \right)^s \ge \frac{3}{2\sqrt{2}}
The equality holds when n=2n = 2.

Finally, consider the left inequality. Denote by 1=d1<d2<<dτ(n)=n1 = d_1 < d_2 < \dots < d_{\tau(n)} = n all divisors of nn. Then σ(n)=i=1τ(n)di\sigma(n) = \sum_{i=1}^{\tau(n)} d_i. Since nd1,nd2,,ndτ(n)\frac{n}{d_1}, \frac{n}{d_2}, \dots, \frac{n}{d_{\tau(n)}} are precisely the divisors of nn, we also have σ(n)=i=1τ(n)ndi\sigma(n) = \sum_{i=1}^{\tau(n)} \frac{n}{d_i}.

For each divisor did_i we also have
di+ndin+1    di2di(n+1)+n0    (ndi)(1di)0,(10) d_i + \frac{n}{d_i} \le n + 1 \iff d_i^2 - d_i(n + 1) + n \le 0 \iff (n - d_i)(1 - d_i) \le 0, \quad (10)
and the equality holds if and only if either di=1d_i = 1 or di=nd_i = n. Now, we can estimate
σ(n)τ(n)=σ(n)+σ(n)2τ(n)=i=1τ(n)di+i=1τ(n)ndi2τ(n)=i=1τ(n)(di+ndi)2τ(n)i=1τ(n)(n+1)2τ(n)=τ(n)(n+1)2τ(n)=n+12. \begin{aligned} \frac{\sigma(n)}{\tau(n)} &= \frac{\sigma(n) + \sigma(n)}{2\tau(n)} = \frac{\sum_{i=1}^{\tau(n)} d_i + \sum_{i=1}^{\tau(n)} \frac{n}{d_i}}{2\tau(n)} = \frac{\sum_{i=1}^{\tau(n)} \left(d_i + \frac{n}{d_i}\right)}{2\tau(n)} \le \\ &\le \frac{\sum_{i=1}^{\tau(n)} (n+1)}{2\tau(n)} = \frac{\tau(n) \cdot (n+1)}{2\tau(n)} = \frac{n+1}{2}. \end{aligned}
The equality holds if and only if it holds for each (10). This is only the case when τ(n)2\tau(n) \le 2. So, the equality holds when either n=1n = 1 or nn is a prime.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.