Олимпиадная задача по комбинаторной геометрии: максимум связных фигур на клетчатом квадрате

Лемма.Всякую связную фигуру, составленную из 101 клетки, можно заключить в прямоугольник с такими сторонами a и b , что a+b=102.

Возьмем две клетки нашей фигуры, имеющие общую сторону. Они образуют прямоугольник 1×2, сумма сторон которого равна 3. В силу связности данной нам фигуры в ней найдется клетка, примыкающая к этому прямоугольнику по стороне. Присоединим к нему эту клетку. Получившуюся конфигурацию из трех клеток можно заключить в прямоугольник с суммой сторон 4, если удлинить на 1 одну из сторон прямоугольника 1×2. Будем повторять описанную процедуру, пока в конфигурацию не войдут все клетки фигуры. Всего процедура будет совершена не более, чем 99 раз, поэтому сумма сторон прямоугольника, в который в итоге окажется заключена фигура, окажется не больше 102.

Излеммысразу следует, что четыре фигуры, равные данной, удастся вырезать всегда: для этого достаточно заключить ее в прямоугольник с суммой сторон 102, а затем вырезать из данного квадрата четыре таких прямоугольника так, как показано на рисунке. Теперь рассмотрим фигуру в форме креста, каждый луч которого состоит из 25 клеток. В ней4×25+1=101клетка.

Если такой крест вырезан из квадрата, то его центр должен лежать вне каемки шириной в 25 клеток, примыкающей к границе квадрата. Это означает, что этот центр должен лежать в квадрате со стороной 52, получающемся после удаления каемки. Разделим этот квадрат на четыре равных квадрата со стороной 26.

Нетрудно видеть, что если из листа бумаги вырезано несколько непересекающихся крестов, то в каждом из этих четырех квадратов может находиться центр только одного креста (иначе два креста будут пересекаться). Поэтому больше четырех крестов из листа вырезать не удастся, что завершает доказательство.