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