Задача 109953
|
|
 |
Условие
Имеется квадрат клетчатой бумаги размером 102×102 клетки и связная фигура неизвестной формы, состоящая из 101 клетки. Какое наибольшее число таких фигур можно с гарантией вырезать из этого квадрата? Фигура, составленная из клеток, называется связной, если любые две ее клетки можно соединить цепочкой ее клеток, в которой любые две соседние клетки имеют общую сторону.Решение
Лемма. Всякую связную фигуру, составленную из 101 клетки, можно заключить в прямоугольник с такими сторонами a и b , что a+b=102.Возьмем две клетки нашей фигуры, имеющие общую сторону. Они образуют прямоугольник 1×2, сумма сторон которого равна 3. В силу связности данной нам фигуры в ней найдется клетка, примыкающая к этому прямоугольнику по стороне. Присоединим к нему эту клетку. Получившуюся конфигурацию из трех клеток можно заключить в прямоугольник с суммой сторон 4, если удлинить на 1 одну из сторон прямоугольника 1×2. Будем повторять описанную процедуру, пока в конфигурацию не войдут все клетки фигуры. Всего процедура будет совершена не более, чем 99 раз, поэтому сумма сторон прямоугольника, в который в итоге окажется заключена фигура, окажется не больше 102.
Из леммы сразу следует, что четыре фигуры, равные данной, удастся вырезать всегда: для этого достаточно заключить ее в прямоугольник с суммой сторон 102, а затем вырезать из данного квадрата четыре таких прямоугольника так, как показано на рисунке. Теперь рассмотрим фигуру в форме креста, каждый луч которого состоит из 25 клеток. В ней 4×25+1=101 клетка.
Если такой крест вырезан из квадрата, то его центр должен лежать вне каемки шириной в 25 клеток, примыкающей к границе квадрата. Это означает, что этот центр должен лежать в квадрате со стороной 52, получающемся после удаления каемки. Разделим этот квадрат на четыре равных квадрата со стороной 26.
Нетрудно видеть, что если из листа бумаги вырезано несколько непересекающихся крестов, то в каждом из этих четырех квадратов может находиться центр только одного креста (иначе два креста будут пересекаться). Поэтому больше четырех крестов из листа вырезать не удастся, что завершает доказательство.
