Question

Петя расставил по окружности 49 фишек, раскрашенных в 10 разных
цветов. Докажите, что найдутся такие два разных цвета, что фишки этих цветов
не стоят рядом.

Answer 1

По принципу Дирихле, на окружности есть не более 4 фишек одного цвета (для определенности будем считать, что красного), т.к. в противном случае всего фишек было бы не менее 5*10=50, а по условию их 49. Тогда у красных фишек не более 4*2=8 соседей (у каждой фишки ровно два соседа, но у двух фишек могут быть общие соседи). Значит, среди остальных 9 цветов найдется такой цвет (например, желтый), что ни у одной красной фишки нет желтого соседа. Следовательно, красные и желтые фишки не стоят рядом, что и требовалось доказать.