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

Проект МЦНМО
при участии
школы 57
Задача 65580
Темы:    [ Индукция в геометрии ]
[ Раскраски ]
[ Системы точек и отрезков. Примеры и контрпримеры ]
[ Простые числа и их свойства ]
[ Деление с остатком ]
Сложность: 5-
Классы: 10,11
В корзину
Прислать комментарий

Условие

В пространстве даны 200 точек. Каждые две из них соединены отрезком, причём отрезки не пересекаются друг с другом. Каждый отрезок покрашен в один из K цветов. Петя хочет покрасить каждую точку в один из этих цветов так, чтобы не нашлось двух точек и отрезка между ними, окрашенных в один цвет. Всегда ли Пете это удастся, если
  a)  K = 7;   б)  K = 10?


Решение

  а) Первый способ. Обозначим  p1 = 13,  p2 = 17,  p3 = 19,  p4 = 23,  p5 = 29,  p6 = 31,  p7 = 37.  Занумеруем точки числами от 1 до 200 и окрасим отрезки, соединяющие точки, номера которых сравнимы по модулю pi, в i-й цвет (условие непротиворечиво:  НОК(pi, pj) > 200).  Тогда в группе точек с номерами, сравнимыми с данным числом по модулю pi, Петя сможет окрасить в i-й цвет не более одной. Значит, всего в i-й цвет он окрасит не больше pi точек. Но  p1 + ... + p7 < 200.  Противоречие.

  Второй способ. Докажем по индукции следующее утверждение: если число цветов n, а число точек не меньше 2n, то ответ отрицательный.
  База  (n = 1)  очевидна.
  Шаг индукции. Разобьём точки на два множества, состоящие не менее чем из  2n–1  точек каждое. В каждом из множеств покрасим отрезки в  n – 1  цвет в соответствии с индуктивным предположением. Все отрезки, соединяющие точки из разных множеств, покрасим оставшимся цветом. Если в каком-то из двух множеств нет точек, покрашенных в последний цвет, то "плохой" отрезок существует по предположению индукции. Если же в обоих множествах есть точки последнего цвета, то соединяющий их отрезок – "плохой".

  б) Покажем, что это не удастся сделать даже для 121 точки. Отождествим точки с точками конечной плоскости 11-го порядка. Выделим на ней 10 направлений (всего их 12) и все отрезки i-го направления покрасим в i-й цвет. Тогда на каждой прямой i-го направления только одна из 11 точек может иметь i-й цвет, то есть точек i-го цвета не больше 11. Но  10·11 < 121.  Противоречие.


Ответ

Не всегда (в обоих случаях).

Замечания

1. Рассуждение, аналогичное приведённому в а), проходит даже для 9 цветов: в качестве чисел pi можно рассмотреть 13, 16, 17, 19, 21, 23, 25, 29, 31.

2. Баллы: 4 + 4.

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

олимпиада
Название Турнир городов
Турнир
Номер 26
Дата 2004/2005
вариант
Вариант весенний тур, основной вариант, 10-11 класс
задача
Номер 7

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

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