Задача 98016

Темы:    [ Принцип Дирихле (прочее) ] [ Отношение порядка ] [ Целочисленные решетки (прочее) ]

Сложность: 4+ Классы: 8,9,10

Условие

Автор: Седракян Н.

Дан 101 прямоугольник с целыми сторонами, не превышающими 100.
Докажите, что среди них найдутся три прямоугольника A, B, C, которые можно поместить друг в друга (так что  A ⊂ B ⊂ C).

Решение

Рассмотрим квадрат 100×100, разбитый на единичные клетки. Назовём m-уголком  (1 ≤ m ≤ 50)  фигуру, состоящую из клетки, стоящей на пересечении m-го столбца слева и m-й строки снизу, а также всех клеток m-го столбца выше неё и всех клеток m-й строки правее неё. Каждый прямоугольник разместим внутри квадрата, совместив его вершину с левой верхней вершиной квадрата и расположив большую сторону вертикально. Определяющей назовём его клетку, противоположную указанной вершине. Для каждого прямоугольника его определяющая клетка принадлежит ровно одному из 50 уголков. Найдутся три прямоугольника, соответствующие одному уголку. Очевидно, они вкладываются друг в друга.

Замечания

1. 7 баллов.

2. Ср. с задачей М1188 из Задачника "Кванта".

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

олимпиада
Название	Турнир городов
Турнир
Номер	10
Дата	1988/1989
вариант
Вариант	весенний тур, основной вариант, 9-10 класс
Задача
Номер	6