Maths Olympiad Prep

Library / /64 of 87

Algebra Difficulty 6.8 National Olympiad Prove it Russia

Let f:RRf: \mathbb{R} \to \mathbb{R} be a continuous function. Let us call a chord a segment of integer length parallel to the axis OxOx whose endpoints belong to the graph y=f(x)y = f(x). It is known that the graph y=f(x)y = f(x) has exactly NN chords, and moreover, among them there is a chord of length 20252025. Find the least possible value of NN.

Solution

Ответ. 4049.

For a natural number nn, define gn(x)=f(x+n)f(x)g_n(x) = f(x+n) - f(x). Then the number of chords of length nn equals the number of zeros of the function gn(x)g_n(x).

As an example, consider the following piecewise linear function ff: f(x)=xf(x) = x for x2024910x \le 2024\frac{9}{10} and f(x)=202492025xf(x) = 20249 \cdot |2025 - x| for x2024910x \ge 2024\frac{9}{10}. Note that for a[0;2025110]a \notin [0; 2025\frac{1}{10}], the function f(x)f(x) takes the value f(a)f(a) only at point aa. Therefore, if gn(x)=0g_n(x) = 0, then both points xx and x+nx+n must lie in the interval [0,2025110][0, 2025 \frac{1}{10}]. In particular, n2025n \le 2025, and the zeros of gn(x)g_n(x) lie in [0;2025110n][0; 2025 \frac{1}{10} - n].

For n=2025n = 2025 and x[0,110]x \in [0, \frac{1}{10}], we have g2025(x)=20248xg_{2025}(x) = 20248x. Thus, g2025(x)g_{2025}(x) has a unique zero at x=0x = 0, meaning the function ff has exactly one chord of length 20252025. For natural n2024n \le 2024, the function gn(x)g_n(x) is monotonically decreasing on [0,2025n][0, 2025 - n] and monotonically increasing on [2025n,2025110n][2025 - n, 2025 \frac{1}{10} - n], with gn(0)>0g_n(0) > 0, gn(2025n)<0g_n(2025 - n) < 0, and gn(2025110n)>0g_n(2025 \frac{1}{10} - n) > 0. Therefore, this function has exactly two zeros, meaning ff has two chords of each length n=1,2,,2024n = 1, 2, \dots, 2024. In total, it has 40494049 distinct chords.

gk(0)=0g_k(0) = 0. The differences dj=f(rj+1)f(rj)d_j = f(r_{j+1}) - f(r_j) satisfy: if rj+1>rjr_{j+1} > r_j then dj=gk(rj)0d_j = g_k(r_j) \ge 0; if rj+1<rjr_{j+1} < r_j then dj=gm(rj+1)d_j = -g_m(r_{j+1}).
The sum dj=0\sum d_j = 0 must contain both positive and negative terms, implying gm(t)>0g_m(t) > 0 for some t(0,k)t \in (0, k). Since gk(0)+gm(k)=gm(0)+gk(m)=0g_k(0) + g_m(k) = g_m(0) + g_k(m) = 0 and gk0g_k \ge 0, we get gm(0)0g_m(0) \le 0 and gm(k)0g_m(k) \le 0. This leads to gmg_m having at least 33 zeros (at 00, kk, and between them), plus gkg_k having at least 11 zero, totaling 44 zeros as required. The case when gk(m)=0g_k(m) = 0 is similar.

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.