Maths Olympiad Prep

Library / /39 of 57

Algebra Difficulty 7.1 National olympiad, round 2 Prove it Russia

Let nn be a positive integer. We have 2n+12n+1 (not necessarily distinct) nonzero integers with a nonzero sum. One needs to put them in places of the stars into an expression x2n+x2n1++x+*x^{2n} + *x^{2n-1} + \cdots + *x + * so that the resulting polynomial would have no integer root. Is it always possible?

Пусть nn — натуральное число. На 2n+12n+1 карточках написано по ненулевому целому числу; сумма всех чисел также ненулевая. Требуется этими карточками заменить звёздочки в выражении x2n+x2n1+...+x+*x^{2n} + *x^{2n-1} + ... + *x + * так, чтобы полученный многочлен не имел целых корней. Обязательно ли это можно сделать?

Solution

Yes.
Put the number with the largest absolute value at x2nx^{2n}; then the only possible integer root is 1-1. This is easily avoidable by permuting the remaining coefficients.

Solution:
Да, обязательно.
Пусть p0,p1,,p2np_0, p_1, \dots, p_{2n} — числа на карточках, причём p2np_{2n} — наибольшее по модулю из них. Поставим pip_i коэффициентом при xix^i. Тогда, если aa — целое число, по модулю не меньшее двойки, то
p2na2n>p2n(a2n1+a2n2++1)p2n1a2n1+p2n2a2n2++p0p2n1a2n1+p2n2a2n2++p0, \begin{aligned} |p_{2n}a^{2n}| &> |p_{2n}|(|a^{2n-1}| + |a^{2n-2}| + \dots + 1) \ge \\ &\ge |p_{2n-1}a^{2n-1}| + |p_{2n-2}a^{2n-2}| + \dots + |p_0| \ge \\ &\ge |p_{2n-1}a^{2n-1}| + |p_{2n-2}a^{2n-2}| + \dots + |p_0|, \end{aligned}
так что aa — не корень полученного многочлена.
Осталось переставить коэффициенты p2n1,p2n2,,p0p_{2n-1}, p_{2n-2}, \dots, p_0 так, чтобы числа 00 и ±1\pm 1 также не были корнями. Числа 00 и 11 в любом случае корнями не являются, поскольку p00p2n+p2n1++p0p_0 \ne 0 \ne p_{2n} + p_{2n-1} + \dots + p_0 по условию. Предположим, что x0=1x_0 = -1 является корнем многочлена при любой перестановке коэффициентов p2n1,p2n2,,p0p_{2n-1}, p_{2n-2}, \dots, p_0. Тогда, если поменять местами pip_i и pi1p_{i-1} (при i=1,2,,2n1i=1, 2, \dots, 2n-1), значение многочлена в x0x_0 не изменится, что возможно лишь при pi=pi1p_i = p_{i-1}. Но тогда наш многочлен имеет вид p2nx2n+p0(x2n1+x2n2++1)p_{2n}x^{2n} + p_0(x^{2n-1} + x^{2n-2} + \dots + 1), и его значение в точке x0=1x_0 = -1 равно p2n0p_{2n} \ne 0. Противоречие.

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.