Задание олимпиады: максимальное количество хорд с одноцветными концами на окружности
Задача
Петя раскрашивает 2006 точек, расположенных на окружности, в 17 цветов. Затем Коля проводит хорды с концами в отмеченных точках так, чтобы концы любой хорды были одноцветны и хорды не имели общих точек (в том числе и общих концов). При этом Коля хочет провести как можно больше хорд, а Петя старается ему помешать. Какое наибольшее количество хорд заведомо сможет провести Коля?
Решение
Заметим, что 2006 = 17·118; поэтому найдутся два цвета, в которые покрашены в сумме не менее 2·118 = 236 точек.
Докажем индукцией по k, что через 2k – 1 точек двух цветов всегда можно провести k – 1 непересекающихся хорд с одноцветными концами.
База (k = 1, 2) очевидна.
Шаг индукции. Пусть k > 2. Тогда среди точек возьмём две одноцветные, стоящие подряд. Соединим их хордой, выбросим и применим предположение индукции к оставшимся точкам.
Выбрав 235 точек двух цветов и применив доказанное утверждение, получаем, что 117 хорд Коля сможет провести всегда. Осталось привести пример, когда больше хорд провести нельзя. Пусть на окружности стоит 17k точек, а Петя покрасит каждую точку в цвет, соответствующий остатку от деления на 17 её номера.
Докажем индукцией по k, что через эти точки можно провести не более k – 1 хорд с выполнением условия.
База очевидна.
Шаг индукции. Пусть проведено некоторое количество хорд. Рассмотрев две соединенные точки A и B на минимальном расстоянии друг от друга, получим такую хорду AB, что на одной из дуг, на которые она делит окружность, нет концов других проведённых хорд. Теперь сотрём хорду AB и уберём с окружности все точки этой дуги, включая один из концов хорды. Мы получили исходную раскраску 17l точек при l < k. Они соединены не более чем l – 1 хордами, поэтому изначально хорд было не больше l – 1 + 1 ≤ k – 1, что и требовалось.
Ответ
117 хорд.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь