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

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

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

Пусть на столе лежат $n$ квадратных листов бумаги. Рассмотрим проекции квадратных листов бумаги на стороны стола. Если поставить стол прямо перед нами, то пусть $A_{1}, A_{2},...., A_{n}$ это горизонтальные проекции, а $B_{1}, B_{2},...., B_{n}$ это вертикальные проекции листов бумаги на стороны стола. Заметим что мы можем выбрать точки $x_{1},x_{2},....,x_{k}$ так чтобы каждой из проекций $A_{1}, A_{2},...., A_{n}$ принадлежала ровно одна точка. Так как все листы бумаги одинакового размера то длины всех проекций равны, тогда выбирая самую нижнюю проекцию где нет выбранной точки, и ставя туда точку мы получаем что таким способом что можем выбрать требуемые точки. Аналогично можно выбрать точки $y_{1},y_{2},....,y_{s}$, для проекций $B_{1}, B_{2},...., B_{n}$. Тогда ставя булавки и точки пересечения прямых перпендикулярных сторонам стола для точек $x_{i},y_{j}$ которые принадлежат соответственно горизонтальной и вертикальной проекциям некоему квадрату, получаем что каждый квадрат прилеплен одной булавкой.