ВсОШ 2021, 9 класс, задача 1
На окружности отмечено точек, каждая окрашена в один из цветов. Оказалось, что среди любых пяти попарно пересекающихся отрезков, концами которых являются различных отмеченных точек, найдутся хотя бы три отрезка, у каждого из которых концы имеют разные цвета. При каком наименьшем это возможно?
(С. Берлов)
Ответ
Ответ.
При .
Решение.
Предположим, что на окружности есть точек одного цвета (скажем, красного). Добавим к ним еще две отмеченных точки, получив десятиугольник . Тогда отрезки попарно пересекаются, и среди них есть три отрезка, у которых все концы красные. Это противоречит условию. Таким образом, точек каждого цвета не больше семи, поэтому , то есть .
При отметим дополнительную, -ю, точку и разделим все отмеченные точки на группы по подряд идущих точек. Каждую группу окрасим своим цветом. Пусть - пять попарно пересекающихся отрезков с концами в отмеченных точках. Можно считать, что точки расположены на окружности именно в этом порядке. Предположим, что отрезок имеет одноцветные концы (скажем, красные). Тогда либо все точки , либо все точки красные. В первом случае максимум две из точек красные. Но тогда три отрезка, не содержащие этих точек, будут иметь разноцветные концы. Второй случай аналогичен.