Условие
На прямоугольном столе лежат равные картонные квадраты k
различных цветов со сторонами, параллельными сторонам стола. Если рассмотреть
любые k квадратов различных цветов, то какие-нибудь два из них
можно прибить к столу одним гвоздем.
Докажите, что все квадраты некоторого цвета
можно прибить к столу 2k-2 гвоздями.
Подсказка
Ведите индукцию по кличеству цветов.
Решение
Докажем утверждение задачи индукцией по количеству цветов n.
База для n=2. Рассмотрим самый левый квадрат K.
Если он первого цвета, то все квадраты второго цвета имеют с ним общую
точку, следовательно, каждый квадрат второго цвета содержит одну из двух
правых вершин квадрата K, следовательно, все квадраты второй системы
можно прибить двумя гвоздями.
Индукционный переход.
Пусть мы доказали утверждение задачи для n цветов, докажем для
(n+1)-го цвета. Рассмотрим все квадраты и выберем из них самый левый
квадрат K. Пусть он покрашен в (n+1)-ый цвет. Все квадраты, пересекающие
K, содержат одну из двух его правых вершин, следовательно, их можно
прибить двумя гвоздями. Уберем со стола все квадраты (n+1)-го цвета и
квадраты других цветов, пересекающие K.
Остались квадраты n различных цветов. Нетрудно доказать, что если выбрать
n квадратов разных цветов, то среди них найдутся два пересекающихся.
(Иначе, добавим квадрат K и получим n+1 попарно не пересекающихся
квадратов разных цветов, что противоречит условию задачи.)
Таким образом, по индукционному предположению, можно выбрать один из цветов
i и прибить 2k-2 гвоздями все оставшиеся на столе квадраты этого цвета.
Убранные квадраты цвета i пересекают самый левый квадрат K,
следовательно, эти квадраты можно прибить, забив два гвоздя в правые
вершины квадрата K.
Источники и прецеденты использования
