Задача
COM-B2-M06-P005 Одноцветная звезда
#5
★★☆☆☆ Уровень 2 из 5
Рёбра из одной вершины к \(2m-1\) другим вершинам покрашены в красный и синий цвета. Докажите, что найдутся \(m\) рёбер одного цвета.
Это усиленный принцип Дирихле.
Если красных рёбер не больше \(m-1\) и синих не больше \(m-1\), то всего рёбер не больше \(2m-2\). Но рёбер \(2m-1\). Значит, один цвет встречается хотя бы \(m\) раз.
Эта форма часто используется внутри доказательств Рамсея.