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