Maths Olympiad Prep

Library / /381 of 397

Algebra Difficulty 7.3 National Olympiad, round 2 Prove it Taiwan

Let SS be the set of all rational numbers in the interval [0,1][0, 1]. Given an infinite sequence of real numbers
{x1,x2,,xk,}, \{x_1, x_2, \dots, x_k, \dots\},
if there exists a function H(x)H(x) mapping SS to the real numbers satisfying:
(i) HH is increasing on [0,12][0, \frac{1}{2}]. That is: for any rational numbers 0ab120 \le a \le b \le \frac{1}{2}, we have H(a)H(b)H(a) \le H(b).
(ii) for any two integers 0<p,0qp0 < p, 0 \le q \le p, we have
H(qp)=k=1qxp+1kk=1qxkp H(\frac{q}{p}) = \frac{\sum_{k=1}^{q} x_{p+1-k} - \sum_{k=1}^{q} x_k}{p}
then we call this sequence of real numbers "fantastic". Find all fantastic sequences.

Solution

All fantastic sequences are: xk=a(klog(k)(k1)log(k1))+cx_k = a(k \log(k) - (k-1) \log(k-1)) + c, where aa is a nonnegative real number, and cc is an arbitrary real number.

First it is easy to see that if {x1,x2,,xk,}\{x_1, x_2, \cdots, x_k, \cdots\} is fantastic, then for any real number cc and positive real number rr, {x1r+c,x2r+c,,xkr+c,}\{\frac{x_1}{r} + c, \frac{x_2}{r} + c, \cdots, \frac{x_k}{r} + c, \cdots\} is also fantastic.
Therefore, without loss of generality assume x1=0x_1 = 0. Let f(p)=i=1pxif(p) = \sum_{i=1}^{p} x_i, then it is easy to see that H(qp)=f(p)f(q)f(pq)pH(\frac{q}{p}) = \frac{f(p)-f(q)-f(p-q)}{p}.
Since H(qp)=H(kpkp)H(\frac{q}{p}) = H(\frac{kp}{kp}), therefore
f(p)f(q)f(pq)p=f(kp)f(kq)f(k(pq))kp \frac{f(p) - f(q) - f(p-q)}{p} = \frac{f(kp) - f(kq) - f(k(p-q))}{kp}
After rearranging terms and simplifying we obtain
(f(kp)kf(p))=(f(kq)kf(q))+(f(k(pq))kf(pq)) (f(kp) - k f(p)) = (f(kq) - k f(q)) + (f(k(p-q)) - k f(p-q))
which holds for all positive integers k,pk, p and non-negative integers 0qp0 \le q \le p. Now fix a positive integer kk, and define gk(p)=f(kp)kf(p)g_k(p) = f(kp) - kf(p), then the above formula becomes
gk(p)=gk(q)+gk(pq) g_k(p) = g_k(q) + g_k(p - q)
This is a standard Cauchy equation; setting q=1q=1 and using mathematical induction, we get gk(p)=pgk(1)=p(f(k)kf(1))=pf(k)g_k(p) = pg_k(1) = p(f(k) - kf(1)) = pf(k) (since f(1)=x1=0f(1) = x_1 = 0), therefore
f(kp)=kf(p)+pf(k) f(kp) = kf(p) + pf(k)
Furthermore, if we fix pp in this formula and use mathematical induction, we can obtain that for any positive integers p,kp, k, f(pk)=pk1kf(p)f(p^k) = p^{k-1}kf(p).

For two positive integers q<pq < p, since qp+q+1<q+1p+q+112\frac{q}{p+q+1} < \frac{q+1}{p+q+1} \le \frac{1}{2} and by the increasing property of H(x)H(x), we have
f(p+q+1)f(q)f(p+1)p+q+1f(p+q+1)f(q+1)f(p)p+q+1 \begin{aligned} \frac{f(p+q+1) - f(q) - f(p+1)}{p+q+1} \le \frac{f(p+q+1) - f(q+1) - f(p)}{p+q+1} \end{aligned}
After rearranging we obtain
f(p+1)f(p)f(q+1)f(q) f(p+1) - f(p) \ge f(q+1) - f(q)
which holds for all p>qp > q. Note that this means f(p)f(p) is a convex function.
From this, we can obtain an obvious inequality: for positive integers p>q>rp > q > r,
f(p)f(q)pqf(p)f(r)prf(q)f(r)qr \frac{f(p) - f(q)}{p - q} \ge \frac{f(p) - f(r)}{p - r} \ge \frac{f(q) - f(r)}{q - r}
This is because
f(p)f(q)pq(pq)(f(q+1)f(q))pq=f(q+1)f(q)=(qr)(f(q+1)f(q))qr=f(q)f(r)qr \begin{aligned} & \frac{f(p) - f(q)}{p - q} \\ \ge & \frac{(p - q)(f(q + 1) - f(q))}{p - q} \\ = & f(q + 1) - f(q) \\ = & \frac{(q - r)(f(q + 1) - f(q))}{q - r} \\ = & \frac{f(q) - f(r)}{q - r} \end{aligned}
And since
f(p)f(r)pr=pqprf(p)f(q)pq+qrprf(q)f(r)qr \frac{f(p) - f(r)}{p - r} = \frac{p - q}{p - r} \frac{f(p) - f(q)}{p - q} + \frac{q - r}{p - r} \frac{f(q) - f(r)}{q - r}
therefore its value lies between the two.

Now suppose f(2)=af(2) = a is known, then a=f(2)=f(2)f(1)f(1)2=H(12)H(0)=0a = f(2) = \frac{f(2)-f(1)-f(1)}{2} = H(\frac{1}{2}) \ge H(0) = 0. According to f(pk)=pk1kf(p)f(p^k) = p^{k-1}kf(p), we can deduce f(2k)=2k1kaf(2^k) = 2^{k-1}ka, that is, when p=2kp = 2^k, f(p)=a2plog2pf(p) = \frac{a}{2}p \log 2p. When p2kp \neq 2^k, we hope to estimate the value of f(p)f(p) using inequalities. For any positive integer mm, there exists a positive integer nn such that 2n+1>pm>2n2^{n+1} > p^m > 2^n, therefore
f(2n+1)f(2n)2n+12nf(pm)f(2n)pm2n \frac{f(2^{n+1}) - f(2^n)}{2^{n+1} - 2^n} \ge \frac{f(p^m) - f(2^n)}{p^m - 2^n}
After rearranging and substituting f(2k)=2k1kaf(2^k) = 2^{k-1}ka we obtain
a(2n1n+(n2+1)(pm2n))f(pm)=pm1mf(p) a(2^{n-1}n + (\frac{n}{2} + 1)(p^m - 2^n)) \geq f(p^m) = p^{m-1}mf(p)
Further we have
f(p)apn+22npm2mapn+22m f(p) \le \frac{apn + 2 - \frac{2^n}{p^m}}{2m} \le \frac{apn + 2}{2m}
From 2n+1>pm>2n2^{n+1} > p^m > 2^n we can deduce n+1m>log2p>nm\frac{n+1}{m} > \log_2 p > \frac{n}{m}, so nm\frac{n}{m} is a rational estimate of log2p\log_2 p. Therefore
f(p)apn+22map2(log2p+2m) f(p) \le \frac{apn + 2}{2m} \le \frac{ap}{2}(\log_2 p + \frac{2}{m})
When mm is very large we obtain
f(p)ap2log2p f(p) \leq \frac{ap}{2} \log_2 p
Similarly, using pm>2n>2n1p^m > 2^n > 2^{n-1} we can obtain
f(pm)f(2n)pm2nf(2n)f(2n1)2n2n1 \frac{f(p^m) - f(2^n)}{p^m - 2^n} \geq \frac{f(2^n) - f(2^{n-1})}{2^n - 2^{n-1}}
After rearranging we obtain
f(p)ap2n+12npmmap2(log2p1m) f(p) \geq \frac{ap}{2} \frac{n + 1 - \frac{2^n}{p^m}}{m} \geq \frac{ap}{2} (\log_2 p - \frac{1}{m})
When mm is very large we then have
f(p)ap2log2p f(p) \geq \frac{ap}{2} \log_2 p
Combining the two inequality estimates together we obtain
f(p)=ap2log2p f(p) = \frac{ap}{2} \log_2 p
Combining a2log2p\frac{a}{2\log_2 p} into a single parameter, and combining with the case p=2kp = 2^k, we obtain
f(p)=aplogp f(p) = ap \log p
which holds for any positive integer, where aa is a nonnegative real number. Therefore
xk=f(k)f(k1)=a(klog(k)(k1)log(k1)) x_k = f(k) - f(k-1) = a(k \log(k) - (k-1) \log(k-1))

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 translated into English from zh; metadata (topic, difficulty) added by this project.