The monic polynomial is called “nice” if its coefficients are in . Given a nice polynomial of degree and it is divisible by , what is the maximum number of non-zero coefficients in ?
Solution
Let . We have for all and is a positive integer. We will group together all exponents divided by with remainder . We have
We see that the right-hand side is a polynomial of degree not exceeding , so to have congruence modulo , we need the right-hand side to be identically . From that, we will get
We see that in the first three sums, there are terms and in the remaining sums, there are terms. So in the first three sums, we choose number and number , and the remaining sums have at least one (otherwise the sum of odd numbers cannot be zero). Thus, there are at least coefficients equal to , so there are at most non-zero coefficients.
To construct, we just choose the coefficients based on the above idea with . The answer is .
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.