Maths Olympiad Prep

Library / /39 of 63

Algebra Difficulty 7.2 National olympiad, round 2 Prove it Japan

Let NN be the set of positive integers. A function f:NNf: N \to N satisfies f(34)=2024f(34) = 2024, and for any positive integers a,b,ca, b, c, there exists a triangle with side lengths a+f(b)a+f(b), b+f(c)b+f(c), c+f(a)c+f(a). Find the smallest possible value of f(100)+f(101)++f(199)f(100) + f(101) + \dots + f(199) under these conditions. Note that three points lying on the same line do not form a triangle.

Solution

The existence of a triangle with side lengths a+f(b)a + f(b), b+f(c)b + f(c), c+f(a)c + f(a) is equivalent to the following conditions:
{a+f(b)<b+f(c)+c+f(a),b+f(c)<c+f(a)+a+f(b),c+f(a)<a+f(b)+b+f(c). \begin{cases} a + f(b) < b + f(c) + c + f(a), \\ b + f(c) < c + f(a) + a + f(b), \\ c + f(a) < a + f(b) + b + f(c). \end{cases}
By symmetry of a,b,ca, b, c, the existence of a triangle with side lengths a+f(b)a + f(b), b+f(c)b + f(c), c+f(a)c + f(a) for any positive integers a,b,ca, b, c is equivalent to the condition that for any positive integers a,b,ca, b, c, we have a+f(b)<b+f(c)+c+f(a)a + f(b) < b + f(c) + c + f(a), or equivalently,
(f(b)b)(f(a)a)<f(c)+c.() (f(b) - b) - (f(a) - a) < f(c) + c. \quad (*)
By considering the cases where a=c=1a = c = 1 and b=c=1b = c = 1 in ()(*), we can establish that 2<f(x)x<2f(1)-2 < f(x) - x < 2f(1) holds for any positive integer xx. Consequently, f(x)xf(x) - x has both a minimum and a maximum value. Denote the minimum and the maximum values as mm and MM respectively, and let r=Mmr = M - m. Then, from ()(*), we have f(x)+x>rf(x) + x > r, which implies f(x)rx+1f(x) \ge r - x + 1. Furthermore, let k=f(34)34=1990k = f(34) - 34 = 1990. Since MkM \ge k, it follows that m=Mrkrm = M - r \ge k - r. Thus, for any positive integer xx, we have f(x)xkrf(x) - x \ge k - r, or equivalently, f(x)k+xrf(x) \ge k + x - r.
Therefore, we have:
f(100)r99,f(101)r100,,f(149)r148,f(150)k+150r,f(151)k+151r,,f(199)k+199r. \begin{aligned} f(100) &\ge r - 99, & f(101) &\ge r - 100, & \dots, & f(149) &\ge r - 148, \\ f(150) &\ge k + 150 - r, & f(151) &\ge k + 151 - r, & \dots, & f(199) &\ge k + 199 - r. \end{aligned}
Since all these inequalities hold, summing them up, we obtain f(100)+f(101)++f(199)50k+2550f(100) + f(101) + \dots + f(199) \ge 50k + 2550.

On the other hand, define:
g(x)={k2+150x(100x149)k2+x149(150x199)x+k(other cases). g(x) = \begin{cases} \frac{k}{2} + 150 - x & (100 \le x \le 149) \\ \frac{k}{2} + x - 149 & (150 \le x \le 199) \\ x + k & \text{(other cases).} \end{cases}
By considering each of three cases, it can be seen that for any positive integer xx, g(x)+xk2+150g(x) + x \ge \frac{k}{2} + 150 and k2149g(x)xk\frac{k}{2} - 149 \le g(x) - x \le k. Therefore, for any positive integers a,b,ca, b, c,
(g(b)b)(g(a)a)k(k2149)<k2+150g(c)+c (g(b) - b) - (g(a) - a) \le k - \left(\frac{k}{2} - 149\right) < \frac{k}{2} + 150 \le g(c) + c
holds, and since g(34)=k+34g(34) = k + 34, gg satisfies the conditions of the problem. For this function gg, g(100)+g(101)++g(199)=50k+2550g(100)+g(101)+\cdots+g(199) = 50k+2550 holds, so the minimum to find is 50k+2550=10205050k+2550 = 102050.

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.