Задание №177284: Турнир городов

6. На доске написано N чисел: все они различны, и одно из них равно 0. Можно взять любой многочлен,
каждый коэффициент которого равен одному из написанных чисел (среди коэффициентов могут быть равные),
и дописать на доску все корни этого многочлена. За несколько таких операций на доске оказались все целые
числа от −2016 по 2016 (и возможно ещё какие-то числа). Найдите наименьшее возможное значение N.
Г.Жуков
Ответ. N = 2.
Из одного нуля ничего получить нельзя. Значит, хотя бы одно число дописать придется.
Покажем, как получить все целые числа от −2016 до 2016 из чисел 0 и a = 2016!.
Получим −1. Это можно сделать с помощью многочлена ax + a. С помощью ax2 − 1 можно получить числа
1 1 1
±√ , из которых с помощью многочлена √ x − √ уже можно получить 1.
a a a

Теперь, если на доске написано число b, с помощью многочлена x+b можно получить −b. Значит, мы можем
сразу дописать на доску −a.
Предположим, на доске написаны числа от 0 до M − 1. Получим M. Числа 0, ..., M − 1 — это цифры в
системе счисления с основанием M. Представим число 2016! в этой системе. Это то же самое, что записать 2016!
в виде значения многочлена f(x) с коэффициентами от 0 до M − 1 в точке M. Для M ⩽ 2016 свободный член
этого многочлена равен 0. Тогда все коэффициенты многочлена f(x) − 2016! уже есть на доске, а его корнем
является число M.
Осталось получить для оставшихся чисел противоположные им.