ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109852
Темы:    [ Системы отрезков, прямых и окружностей ]
[ Раскраски ]
[ Индукция в геометрии ]
[ Системы точек ]
[ Наименьшее или наибольшее расстояние (длина) ]
[ Деление с остатком ]
Сложность: 4
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Петя раскрашивает 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 хорд.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2006
Этап
Вариант 5
Класс
Класс 9
задача
Номер 06.5.9.3
олимпиада
Название Всероссийская олимпиада по математике
год
Год 2006
Этап
Вариант 5
Класс
Класс 10
задача
Номер 06.5.10.3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .