ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109953
Темы:    [ Геометрия на клетчатой бумаге ]
[ Связность. Связные множества ]
[ Замощения костями домино и плитками ]
Сложность: 5
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Имеется квадрат клетчатой бумаги размером 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.

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

Ответ

4.00

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1998
Этап
Вариант 4
Класс
Класс 9
задача
Номер 98.4.9.4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .