Задача 35522

Темы:    [ Разрезания на части, обладающие специальными свойствами ] [ Индукция (прочее) ]

Сложность: 3 Классы: 8,9

Условие

В клетчатом квадрате 64*64 вырезали одну из клеток. Докажите, что оставшуюся часть квадрата можно разрезать на уголки из трех клеток.

Подсказка

Доказывайте общее утверждение для квадрата 2ⁿ*2ⁿ клеток.

Решение

Будем доказывать общее утверждение для квадрата 2ⁿ*2ⁿ клеток с вырезанной клеткой. Для n=1 это утверждение очевидно: если из квадрата 2*2 вырезана одна клетка,то оставшаяся часть квадрата - это уголок из трех клеток. Пусть это утверждение верно для квадрата 2^n-1*2^n-1 клеток с вырезанной клеткой. Итак, пусть в квадрате 2ⁿ*2ⁿ клеток вырезана одна из клеток. Разрежем этот квадрат на 4 квадрата 2^n-1*2^n-1 клеток. Вырезанная клетка попала в один из этих четырех квадратов. Из остальных трех квадратов можно вырезать по одной угловой клетке так, чтобы они образовывали уголок из трех клеток (см. картинку). Вырежем этот уголок. Оставшаяся часть представляет собой четыре квадрата 2^n-1*2^n-1 клеток, в каждом их которых вырезано по клетке. По предположению индукции каждый из этих квадратов можно разрезать на уголки. Тем самым, и квадрат 2ⁿ*2ⁿ клеток с вырезанной клеткой можно разрезать на уголки.

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

web-сайт

задача