Maths Olympiad Prep

Library / /282 of 520

Algebra Difficulty 7.0 National olympiad Find the answer

Given a polynomial f(x)=x2020+i=02019cixif(x)=x^{2020}+\sum_{i=0}^{2019} c_ix^i, where ci{1,0,1}c_i \in \{ -1,0,1 \}. Denote NN the number of positive integer roots of f(x)=0f(x)=0 (counting multiplicity). If f(x)=0f(x)=0 has no negative integer roots, find the maximum of NN.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To find the maximum number of positive integer roots N N of the polynomial f(x)=x2020+i=02019cixi f(x) = x^{2020} + \sum_{i=0}^{2019} c_i x^i where ci{1,0,1} c_i \in \{-1, 0, 1\} , and given that f(x)=0 f(x) = 0 has no negative integer roots, we proceed as follows:

1. Construct a Polynomial with Positive Integer Roots:
Consider the polynomial f(x)=(x1)(x31)(x71)(x131)(x251)(x491)(x991)(x1991)(x3991)(x7991)x426 f(x) = (x-1)(x^3-1)(x^7-1)(x^{13}-1)(x^{25}-1)(x^{49}-1)(x^{99}-1)(x^{199}-1)(x^{399}-1)(x^{799}-1)x^{426} .

- This polynomial has roots at x=1 x = 1 with multiplicity 1, x=13 x = \sqrt[3]{1} with multiplicity 3, x=17 x = \sqrt[7]{1} with multiplicity 7, and so on.
- The exponents 1,3,7,13,25,49,99,199,399,799 1, 3, 7, 13, 25, 49, 99, 199, 399, 799 are chosen such that their sum plus the exponent 426 equals 2020.

2. Verify the Polynomial:
- The polynomial f(x) f(x) constructed above is valid because it has the form x2020+i=02019cixi x^{2020} + \sum_{i=0}^{2019} c_i x^i with ci{1,0,1} c_i \in \{-1, 0, 1\} .
- The polynomial has 10 positive integer roots: 1,13,17,113,125,149,199,1199,1399,1799 1, \sqrt[3]{1}, \sqrt[7]{1}, \sqrt[13]{1}, \sqrt[25]{1}, \sqrt[49]{1}, \sqrt[99]{1}, \sqrt[199]{1}, \sqrt[399]{1}, \sqrt[799]{1} .

3. Prove the Maximum Number of Positive Integer Roots:
- Suppose N>10 N > 10 . Then N11 N \geq 11 .
- If N11 N \geq 11 , then (x1)11 (x-1)^{11} must divide f(x) f(x) .
- Evaluate f(1) f(-1) :
f(1)=(1)2020+i=02019ci(1)i=1+i=02019ci(1)i f(-1) = (-1)^{2020} + \sum_{i=0}^{2019} c_i (-1)^i = 1 + \sum_{i=0}^{2019} c_i (-1)^i
- Since ci{1,0,1} c_i \in \{-1, 0, 1\} , the maximum absolute value of f(1) f(-1) is:
f(1)1+i=020191=2021 |f(-1)| \leq 1 + \sum_{i=0}^{2019} 1 = 2021
- However, if (x1)11 (x-1)^{11} divides f(x) f(x) , then 211 2^{11} must divide f(1) f(-1) , implying:
f(1)211=2048 |f(-1)| \geq 2^{11} = 2048
- This is a contradiction because 2021<2048 2021 < 2048 .

Therefore, the maximum number of positive integer roots N N is 10.

The final answer is 10 \boxed{ 10 } .

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.