Математикадан республикалық олимпиада, 2002-2003 оқу жылы, 10 сынып

Қағаздар ауданы 2003 болатын тең екі квадрат қиылып алынған. Әрбір квадрат ауданы 1-ге тең 2003 көпбұрышқа бөлшектенген. Сонан соң екі квадрат беттестіріледі. Осы қабаттасқан екі квадрат қағазды әрбір квадраттағы әрбір көпбұрыш тесілетіндей етіп инемен 2003 рет тесуге болатынын дәлелдеңіздер.

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

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

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