Олимпиадная задача по планиметрии и комбинаторной геометрии от Дольникова В. Л. для 8–11 класса
Задача
На прямоугольном столе лежат равные картонные квадраты 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.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь