Find all polynomials such that has nonnegative integer coefficients, and .
Hong Kong competition problems
Solution
The only polynomial is .
Suppose one of the coefficients of , say the coefficient of , is at least . Define . Then and . Also, the coefficients of are nonnegative integers. Repeating the same process, since the sequence of nonnegative integers is strictly decreasing, the process must end at some step. Then we obtain a polynomial with coefficients or such that and .
Since the binary representation of is , we know that is uniquely determined, and is given by
As , the equality of should hold. This means we do not need to carry out any process, and must be the same as .
Want a route through all this instead of an archive? The track
puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.