ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 34987
Темы:    [ Покрытия ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Существуют ли 100 таких прямоугольников, что ни один из них нельзя покрыть остальными 99-ю?

Подсказка

Выбирайте прямоугольники последовательно один за другим, каждый следующий - намного тоньше и меньше по площади, чем предыдущий.

Решение

Будем выбирать прямоугольники последовательно один за другим. В качестве первого прямоугольника возьмем квадрат со стороной 1. Пусть si - площадь i-го прямоугольника, li - длина его большей стороны (по параметрам si,li прямоугольник восстанавливается, причем однозначно). Обозначим также через di длину диагонали i-го прямоугольника, таким образом, di есть максимальная возможная длина проекции i-го прямоугольника на прямую. Имеем: s1=1, l1=1, d1=21/2. Если первые k-1 прямоугольников заданы (т.е. определены значения si, li для всех i от 1 до k-1), то определяем sk, lk следующим образом. Положим sk=sk-1/4 (таким образом, si=4-(i-1)); также в качестве lk выберем некоторое число, большее 2(d1+d2+...+dk-1). (Можно представлять себе, что каждый следующий прямоугольник намного тоньше и меньше по площади, чем предыдущий.) Покажем, что определенные таким образом прямоугольники удовлетворяют условию, т.е. для каждого k от 1 до 100 прямоугольник с номером k невозможно покрыть остальными прямоугольниками. Предположим противное - прямоугольник с некоторым номером n покрыт остальными прямоугольниками. Условие ln>2(d1+d2+...+dn-1) означает, что прямоугольники с номерами 1,2,...,n-1 при проектировании их на большую сторону прямоугольника с номером n, покрывают меньше половины этой стороны. Это означает, что не менее половины площади n-ого прямоугольника не покрывается прямоугольниками с номерами 1,2,...,n-1, т.е. покрывается прямоугольниками с номерами n+1,n+2,...,100. Отсюда следует следующее неравенство на площади: sn/2<sn+1+sn+2+...+s100 или 4-(n-1)/2<4-n+4-(n+1)+...+4- 99. Последнее неравенство преобазуется к виду 2-2n+1<2-2n+2-2n-2+...+2- 198, откуда получаем (сокращая на 2-2n+1): 1<1/2+1/8+...+2-199+2n, что неверно (число 1 разлагается в бесконечную сумму 1=1/2+1/4+1/8+...).

Ответ

существуют.

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

web-сайт
задача

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы, Московского института открытого образования и ФЦП "Кадры" .