Maths Olympiad Prep

Library / /209 of 397

Algebra Difficulty 5.9 AIME, harder Prove it Taiwan

Consider all polynomials with integer coefficients of the form f(x)=(xa1)(xa2)(xa3)(xa100)f(x) = (x - a_1)(x - a_2)(x - a_3)\cdots(x - a_{100}), where a1,a2,,a100a_1, a_2, \cdots, a_{100} are arbitrary real numbers. Find the maximum possible value of {a1}+{a2}++{a100}\{a_1\} + \{a_2\} + \cdots + \{a_{100}\}.

Note: Define {x}=x[x]\{x\} = x - [x], where [x][x] is the greatest integer not exceeding xx.

Solution

Since {x}<1\{x\} < 1 holds for any xx, we have {a1}+{a2}++{a100}<100\{a_1\} + \{a_2\} + \cdots + \{a_{100}\} < 100; also, by the relation between roots and coefficients, i=1100ai-\sum_{i=1}^{100} a_i is the coefficient of the x99x^{99} term of f(x)f(x), and hence must be an integer, so
{a1}+{a2}++{a100}99. \{a_1\} + \{a_2\} + \cdots + \{a_{100}\} \le 99.
We now show that there exists an f(x)f(x) such that {a1}+{a2}++{a100}=99\{a_1\} + \{a_2\} + \cdots + \{a_{100}\} = 99. Consider the function

f(x)=x(x2)(x4)(x6)(x198)+(x1)(x3)(x197)f(x) = x(x-2)(x-4)(x-6)\cdots(x-198) + (x-1)(x-3)\cdots(x-197)

Substituting values for checking, it is easy to see that f(1)f(0),f(1)f(2),,f(197)f(198)f(-1)f(0), f(1)f(2), \cdots, f(197)f(198) are all less than 0, so by Newton's method for locating roots, f(x)f(x) has a root in each of the 100 intervals (1,0),(1,2),(3,4),,(197,198)(-1, 0), (1, 2), (3, 4), \cdots, (197, 198). Therefore f(x)f(x) has 100 real roots, satisfying the conditions required by the problem, and
[a1]+[a2]++[a100]=1+1+3++197 [a_1] + [a_2] + \cdots + [a_{100}] = -1 + 1 + 3 + \cdots + 197
But the coefficient of the x99x^{99} term of f(x)f(x) is (2+4+6++198)+1-(2+4+6+\cdots+198)+1, so by the relation between roots and coefficients, we have
a1+a2++a100=2+4+6++1981 a_1 + a_2 + \cdots + a_{100} = 2 + 4 + 6 + \cdots + 198 - 1
Therefore

{a1}+{a2}++{a100}=(a1+a2++a100)([a1]+[a2]++[a100])=(2+4+6++1981)(1+3+5++1971)=99\begin{align*} \{a_1\} + \{a_2\} + \cdots + \{a_{100}\} &= (a_1 + a_2 + \cdots + a_{100}) - ([a_1] + [a_2] + \cdots + [a_{100}]) \\ &= (2 + 4 + 6 + \cdots + 198 - 1) \\ &\quad -(1 + 3 + 5 + \cdots + 197 - 1) \\ &= 99 \end{align*}

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.