Разделы 
Дополнительно
Задача по математике - 3444
2019-06-03 
В пространстве даны 200 точек. Каждые две из них соединены отрезком, причём отрезки не пересекаются друг с другом. В распоряжении двух игроков имеются краски $k$ цветов. Первый игрок красит каждый отрезок в один из $k$ цветов, затем второй игрок красит в один из тех же цветов каждую точку. Если найдутся две точки и отрезок между ними, окрашенные в один цвет, выигрывает первый игрок, в противном случае второй. Докажите, что первый может гарантировать себе выигрыш, если а) $k = 7$, б) $k = 10$.
Решение:
а) Докажем по индукции следующее утверждение: если число цветов $k$, а число точек не меньше $2k$, то первый может гарантировать себе победу.
При $k = 1$ утверждение очевидно. Пусть оно доказано для $k - 1$ цвета, докажем его для $k$ цветов. Выберем произвольное множество, состоящее из $2k$ точек. Разобьем его на два подмножества, состоящие из $2^{k-1}$ точек каждое. Покрасим отрезки, соединяющие точки, лежащие в одном подмножестве, в $k - 1$ цвет в соответствии с индуктивным предположением. Все отрезки, соединяющие точки из разных подмножеств, покрасим оставшимся $k$-м цветом. Теперь посмотрим, как покрасил выбранные $2k$ точек второй игрок. Если в каком-то из двух подмножеств нет точек, покрашенных в $k$-й цвет, то искомый отрезок существует по предположению индукции. Если же в обоих множествах есть точки, покрашенные в $k$-й цвет, то соединяющий их отрезок - искомый.
б) Докажем, что первый игрок может покрасить требуемым образом отрезки, соединяющие 121 точку. Занумеруем точки парами чисел $(a, b)$, где $a$ и $b$ - числа от 1 до 11. Рассмотрим различные точки $(a_1, b_1)$ и $(a_2, b_2)$. Заметим, что найдется не более одного такого $k$, что $(a_2 - a_1) - k(b_2 - b_1)$ делится на 11 (для доказательства воспользуйтесь тем, что 11 - простое число, см. факт 9). При $k = 0, \cdots, 9$ покрасим отрезок, соединяющий такие точки, цветом $k + 1$.
Выберем произвольный цвет. Легко видеть, что если две точки соединены с третьей отрезками этого цвета, то между собой они соединены отрезком того же цвета. Таким образом, точки разбиваются на несколько множеств (классов эквивалентности) так, что все отрезки между точками из одного множества покрашены в выбранный цвет.
Зафиксируем точку $(a_1, b_1)$. Нетрудно убедиться, что для любого $b_2$ существует ровно одно $a_2$ такое, что отрезок между $(a_1, b_1)$ и $(a_2, b_2)$ покрашен в данный цвет. Поэтому для каждого цвета точки разбиваются на 11 множеств по 11 точек в каждом. Теперь покрасим оставшиеся отрезки произвольным образом.
Как бы второй игрок ни покрасил точки, найдутся 12 точек одного цвета. Рассмотрим разбиение на 11 множеств, соответствующее этому цвету. Найдутся две точки, попавшие в одно множество. Соединяющий их отрезок - искомый.
В пространстве даны 200 точек. Каждые две из них соединены отрезком, причём отрезки не пересекаются друг с другом. В распоряжении двух игроков имеются краски $k$ цветов. Первый игрок красит каждый отрезок в один из $k$ цветов, затем второй игрок красит в один из тех же цветов каждую точку. Если найдутся две точки и отрезок между ними, окрашенные в один цвет, выигрывает первый игрок, в противном случае второй. Докажите, что первый может гарантировать себе выигрыш, если а) $k = 7$, б) $k = 10$.
Решение:
а) Докажем по индукции следующее утверждение: если число цветов $k$, а число точек не меньше $2k$, то первый может гарантировать себе победу.
При $k = 1$ утверждение очевидно. Пусть оно доказано для $k - 1$ цвета, докажем его для $k$ цветов. Выберем произвольное множество, состоящее из $2k$ точек. Разобьем его на два подмножества, состоящие из $2^{k-1}$ точек каждое. Покрасим отрезки, соединяющие точки, лежащие в одном подмножестве, в $k - 1$ цвет в соответствии с индуктивным предположением. Все отрезки, соединяющие точки из разных подмножеств, покрасим оставшимся $k$-м цветом. Теперь посмотрим, как покрасил выбранные $2k$ точек второй игрок. Если в каком-то из двух подмножеств нет точек, покрашенных в $k$-й цвет, то искомый отрезок существует по предположению индукции. Если же в обоих множествах есть точки, покрашенные в $k$-й цвет, то соединяющий их отрезок - искомый.
б) Докажем, что первый игрок может покрасить требуемым образом отрезки, соединяющие 121 точку. Занумеруем точки парами чисел $(a, b)$, где $a$ и $b$ - числа от 1 до 11. Рассмотрим различные точки $(a_1, b_1)$ и $(a_2, b_2)$. Заметим, что найдется не более одного такого $k$, что $(a_2 - a_1) - k(b_2 - b_1)$ делится на 11 (для доказательства воспользуйтесь тем, что 11 - простое число, см. факт 9). При $k = 0, \cdots, 9$ покрасим отрезок, соединяющий такие точки, цветом $k + 1$.
Выберем произвольный цвет. Легко видеть, что если две точки соединены с третьей отрезками этого цвета, то между собой они соединены отрезком того же цвета. Таким образом, точки разбиваются на несколько множеств (классов эквивалентности) так, что все отрезки между точками из одного множества покрашены в выбранный цвет.
Зафиксируем точку $(a_1, b_1)$. Нетрудно убедиться, что для любого $b_2$ существует ровно одно $a_2$ такое, что отрезок между $(a_1, b_1)$ и $(a_2, b_2)$ покрашен в данный цвет. Поэтому для каждого цвета точки разбиваются на 11 множеств по 11 точек в каждом. Теперь покрасим оставшиеся отрезки произвольным образом.
Как бы второй игрок ни покрасил точки, найдутся 12 точек одного цвета. Рассмотрим разбиение на 11 множеств, соответствующее этому цвету. Найдутся две точки, попавшие в одно множество. Соединяющий их отрезок - искомый.
