Республиканская олимпиада по математике, 2003 год, 10 класс

Из листа бумаги вырезали два квадрата площади 2003. Каждый квадрат разделен на 2003 непересекающихся многоугольника площади 1. Затем два квадрата накладывают друг на друга. Докажите, что полученный двойной слой бумаги можно проколоть иголкой 2003 раз таким образом, что каждый многоугольник на каждом квадрате будет проколот по одному разу.

Комментарий/решение

Рассмотрим двудольный граф где двудольными множествами являются 2003 многоугольника на каждом листе бумаги если соединить две вершины из обоих двудольных множеств тогда и только тогда когда их многоугольники имеют непустой пересечение при размещении друг над другом.Рассмотрим подмножество X одного из этих двудольных множеств.Это подмножество имеет площадь |X| так как все многоугольники имеют площадь 1.Соседнее множество Р(Х) имеет площадь |P(X)|.Однако обратите внимание, что область, ограниченная Х, является лишь подмножеством области

ограниченной Р(Х).Таким образом,|X|$\geq$|P(X)| для любого подмножества Х,и по теореме Холла существует паросоэетание из одного набора многоугольников в другой.Мы используем это сопоставление, чтобы найти подходящие положения для иголок.