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

Проект МЦНМО
при участии
школы 57
Задача 97878
Темы:    [ Разрезания на параллелограммы ]
[ Прямоугольные параллелепипеды ]
[ Комбинаторная геометрия (прочее) ]
Сложность: 5
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

  а) Квадрат разбит на прямоугольники. Цепочкой называется такое подмножество K множества этих прямоугольников, что существует сторона S квадрата, целиком закрытая проекциями прямоугольников из K, но при этом ни в какую точку S не проектируются внутренние точки двух прямоугольников из K (мы относим к прямоугольнику и его стороны). Доказать, что любые два прямоугольника разбиения входят в некоторую цепочку.

  б) Аналогичная задача для куба, разбитого на прямоугольные параллелепипеды (в определении цепочки нужно заменить сторону на ребро).


Решение

  а) Будем считать, что одна из сторон квадрата вертикальна. Назовём прямоугольники связанными, если они пересекаются одной вертикальной или горизонтальной прямой. (В частности, прямоугольники, имеющие общую вершину, связаны.) Связанные прямоугольники входят в цепочку, "нанизанную" на эту прямую.
  Пусть прямоугольники A и B не связаны. Тогда (с точностью до поворота квадрата) один из них находится левее и выше другого (см. рис.).

  Рассмотрим ближайшую к B вершину прямоугольника A. К ней примыкает (справа или снизу; далее считаем, что справа) прямоугольник С, который имеет с А общую вершину и часть стороны. Заметим, что достаточно соединить цепочкой B и C. Действительно, если эта цепочка горизонтальна, удалим из неё все прямоугольники, лежащие левее С, заменив их на А и прямоугольники, лежащие левее А вдоль некоторой горизонтальной прямой, – получится цепочка, соединяющая В и А. Если же эта цепочка вертикальна, то удалим из неё С и все прямоугольники, лежащие выше С, включим А и аналогично продолжим вверх.
  Для построения цепочки, соединяющей B и C рассуждение можно повторить. На каждом шаге, прямоугольники, которые нужно соединить, сближаются, так что в конце концов они станут связанными.

  б) Рассуждения аналогичны. Объясним более подробно переход от параллелепипеда А к параллелепипеду C. Окрестность вершины параллелепипеда А, ближайшей в B, разбивается на восемь октантов. Один из них "занят" параллелепипедом А, а остальные распределяются по соседним параллелепипедам. При этом соседний параллелепипед может "занимать" один, два или четыре октанта. Ввиду нечётности числа 7 найдётся параллелепипед, занимающий ровно один октант (он может иметь с А только общую вершину или общие вершину и часть грани). В любом случае, соединив его цепочкой с B, мы сможем "переделать" эту цепочку, в цепочку, соединяющую А и B.

Замечания

Баллы: 12 + 12.

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

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

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

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

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