Maths Olympiad Prep

Library / /18 of 36

Algebra Difficulty 5.8 AIME, harder Prove it Saudi Arabia

The monic polynomial P(x)P(x) is called “nice” if its coefficients are in {1,0,1}\{-1, 0, 1\}. Given a nice polynomial P(x)P(x) of degree 20252025 and it is divisible by x71x^7 - 1, what is the maximum number of non-zero coefficients in P(x)P(x)?

Solution

Let f(x)=x71f(x) = x^7 - 1. We have x7k+rxr(modf(x))x^{7k+r} \equiv x^r \pmod{f(x)} for all r=0,1,,6r = 0, 1, \ldots, 6 and kk is a positive integer. We will group together all exponents divided by 77 with remainder rr. We have
P(x)=a2025x2025++a2x2+a1x+a0(a0+a7++a2023)+(a1+a8++a2024)x++(a6+a13++a2022)x6(modf(x)). \begin{aligned} P(x) &= a_{2025}x^{2025} + \cdots + a_2x^2 + a_1x + a_0 \\ &\equiv (a_0 + a_7 + \cdots + a_{2023}) + (a_1 + a_8 + \cdots + a_{2024})x + \cdots \\ &\quad + (a_6 + a_{13} + \cdots + a_{2022})x^6 \pmod{f(x)}. \end{aligned}
We see that the right-hand side is a polynomial of degree not exceeding 66, so to have congruence 00 modulo f(x)f(x), we need the right-hand side to be identically 00. From that, we will get
i=0289a7i=i=0289a7i+1=i=0289a7i+2=i=0288a7i+3=i=0288a7i+4=i=0288a7i+5=i=0288a7i+6=0. \sum_{i=0}^{289} a_{7i} = \sum_{i=0}^{289} a_{7i+1} = \sum_{i=0}^{289} a_{7i+2} = \sum_{i=0}^{288} a_{7i+3} = \sum_{i=0}^{288} a_{7i+4} = \sum_{i=0}^{288} a_{7i+5} = \sum_{i=0}^{288} a_{7i+6} = 0.
We see that in the first three sums, there are 290290 terms and in the remaining sums, there are 289289 terms. So in the first three sums, we choose 145145 number 11 and 145145 number 1-1, and the remaining sums have at least one 00 (otherwise the sum of 289289 odd numbers cannot be zero). Thus, there are at least 44 coefficients equal to 00, so there are at most 20264=20222026 - 4 = 2022 non-zero coefficients.

To construct, we just choose the coefficients based on the above idea with a20250a_{2025} \neq 0. The answer is 20222022.

2022\boxed{2022}

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.