Задача 65580

Темы:    [ Индукция в геометрии ] [ Раскраски ] [ Системы точек и отрезков. Примеры и контрпримеры ] [ Простые числа и их свойства ] [ Деление с остатком ]

Сложность: 5- Классы: 10,11

Условие

Автор: Конягин С.В.

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

Решение

  а) Первый способ. Обозначим  p₁ = 13,  p₂ = 17,  p₃ = 19,  p₄ = 23,  p₅ = 29,  p₆ = 31,  p₇ = 37.  Занумеруем точки числами от 1 до 200 и окрасим отрезки, соединяющие точки, номера которых сравнимы по модулю p_i, в i-й цвет (условие непротиворечиво:  НОК(p_i, p_j) > 200).  Тогда в группе точек с номерами, сравнимыми с данным числом по модулю p_i, Петя сможет окрасить в i-й цвет не более одной. Значит, всего в i-й цвет он окрасит не больше p_i точек. Но  p₁ + ... + p₇ < 200.  Противоречие.

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

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

Ответ

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

Замечания

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

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

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

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