Олимпиадная задача: количество ненулевых коэффициентов в многочлене — задача Сендерова

  Ясно, что существуют требуемые многочлены с 1001 и 1000 ненулевыми коэффициентами (например,  (2x + 2)¹⁰⁰⁰ – (x + 1)¹⁰⁰⁰  и

(2x + 1)¹⁰⁰⁰ – (x + 1)¹⁰⁰⁰).

  Предположим, что в нашем многочлене есть два коэффициента, равных нулю – при xⁱ и x^j  (i > j).  Тогда  aⁱb^1000–i = cⁱd^1000–i,

a^jb^1000–j = c^jd^1000–j,  то есть     Отсюда  

  При замене  ax + b  на  (– a)x + (–b)  наш многочлен не изменится. Поэтому можно считать, что  a = c.  Тогда, если  b = d,  то итоговый многочлен нулевой, а если  d = – b,  то в полученном многочлене  (ax + b)¹⁰⁰⁰ – (ax – b)¹⁰⁰⁰  обнуляются в точности коэффициенты при чётных степенях x, то есть получается 500 ненулевых коэффициентов.