Непрерывное математическое образование

задача Ф.Петрова с ВсОШ-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 нулевая — так как все они имеют нулевую степень хотя бы по одной переменной

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

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

Telegram

Непрерывное математическое образование

Пусть карту — или посто граф — можно раскрасить в N цветов (так, что соседние вершины имеют разные цвета).

А если для каждой вершины зафиксирован свой набор из N разрешенных цветов, получится ли выбрать из них правильную раскраску? На первый взгляд может…

www.group-telegram.com/us/cme_channel.com/3766

6.49K viewsedited  Jun 2, 2024 at 22:24

задача Ф.Петрова с ВсОШ-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 нулевая — так как все они имеют нулевую степень хотя бы по одной переменной

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

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

BY Непрерывное математическое образование