Maths Olympiad Prep

Library / /77 of 104

Number theory Difficulty 6.5 National Olympiad Prove it Bulgaria

Problem:
Let aa, bb and nn be positive integers. Denote by K(n)K(n) the number of the representations of 11 as a sum of nn numbers of the form 1k\frac{1}{k}, where kk is a positive integer. Let L(a,b)L(a, b) be the least positive integer mm such that the equation i=1m1xi=ab\sum_{i=1}^{m} \frac{1}{x_{i}}=\frac{a}{b} has a solution in positive integers and set L(b)=max{L(a,b),1ab}L(b)=\max \{L(a, b), 1 \leq a \leq b\}. Prove that the number of the positive divisors of bb does not exceed 2L(b)+K(L(b)+2)2 L(b)+K(L(b)+2).

Solution

Solution:
The function K(n)K(n) is increasing for n3n \geq 3, since i=1n1xi=1\sum_{i=1}^{n} \frac{1}{x_{i}}=1 implies that
i=1n11xi+1xn+1+1xn(xn+1)=1 \sum_{i=1}^{n-1} \frac{1}{x_{i}}+\frac{1}{x_{n}+1}+\frac{1}{x_{n}(x_{n}+1)}=1
Thus it is enough to find tL(b)t \leq L(b) such that K(t+2)+2L(b)d(b)K(t+2)+2 L(b) \geq d(b), where d(b)d(b) is the number of the distinct positive integers that divide bb. Let tt be the minimal positive integer, for which the equation i=1t1xi=11b\sum_{i=1}^{t} \frac{1}{x_{i}}=1-\frac{1}{b} has a solution. Then tL(b)t \leq L(b). Fix now tt, bb, x1,,xtx_{1}, \ldots, x_{t}.

Note that the numbers of the solution of the equation 1y1+1y2=1b\frac{1}{y_{1}}+\frac{1}{y_{2}}=\frac{1}{b} such that bb divides y2y_{2} and y1y2y_{1} \leq y_{2}, is equal to d(b)d(b). Indeed, if 1b=1y1+1kb\frac{1}{b}=\frac{1}{y_{1}}+\frac{1}{k b} for some k2k \geq 2, then y1=b+bk1y_{1}=b+\frac{b}{k-1}. So k1k-1 divides bb and there are exactly d(b)d(b) possibilities for kk.

Hence K(t+2)K(t+2) is not less than d(b)d(b) minus the number of the cases, when yi=xjy_{i}=x_{j}. This cases are at most 2L(b)2 L(b) which implies the desired inequality.

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.