задача Ф.Петрова с ВсОШ-2007: доказать, что цикл длины 100 является списочно раскрашиваемым в 2 цвета — или, другими словами,

если каждой вершине 100-угольника написано по два различных числа, то можно так вычеркнуть по одному числу в каждой вершине, чтобы оставшиеся числа в каждых двух соседних вершинах были различными

доказать это можно так

рассмотрим многочлен
P:=(x1-x2)(x2-x3)(x3-x4)…(x100-x1)

мы хотим доказать, что если для каждой переменной есть два разрешенных варианта, то для какого-то из выборов P в соответствующей точке не равен нулю

а это следует из того, что коэффициент при мономе x1 x2 … x100 ненулевой

(
действительно, пусть для переменной x1 разрешены значения a и b — тогда перейдем от многочлена P(x1,…) к многочлену P(b,…)-P(a,…); потом сделаем то же по следующей переменной и т.д.

если для каждого из выборов значение P нулевое, то мы в итоге получим 0

с другой стороны, эта операция аддитивная, на мономе x1 x2 … x100 она ненулевая, а на всех остальных мономах из P нулевая — так как все они имеют нулевую степень хотя бы по одной переменной

противоречие
)

доказанное в скобках утверждение — частный случай “комбинаторной теоремы о нулях” и