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