Прямоугольник из плиток 3 × 4: почему НОК — ещё не ответ

Быстрое рассуждение о делимости даёт здесь ответ за одну строчку. Настоящий ответ вдвое больше, и разница поучительна.

Задача

Прямоугольник нарисован на клетчатой бумаге, одна его сторона равна $14$ клеткам. Его разрезают по линиям сетки на плитки $3 \times 4$ клетки; плитки можно поворачивать. Какую наименьшую площадь может иметь такой прямоугольник?

Догадка

Пусть вторая сторона равна $n$ клеткам: площадь равна $14n$ и делится на $12$ — это площадь плитки. Наименьшее такое число: $\text{НОК}(12, 14) = 84$. Ответ — $84$.

Рассуждение выглядит безупречно, и число получается складное: $84 = 14 \times 6$. Но делимость — это только запрет: она говорит, какие площади невозможны, и молчит о том, какие возможны. Прямоугольник $14 \times 6$ ещё нужно суметь разрезать. Попробуем — и не получится.

Рассуждение

Докажем, что прямоугольник $14 \times 6$ разрезать нельзя. Посмотрим на один вертикальный столбец клеток — полоску ширины $1$ и высоты $6$. Каждая плитка, задевающая эту полоску, отрезает от неё кусок высоты $3$ (плитка лежит, $4 \times 3$) или кусок высоты $4$ (плитка стоит, $3 \times 4$).

Может ли в столбце оказаться кусок высоты $4$? Тогда на остаток приходится $6 - 4 = 2$ клетки, а куски бывают только по $3$ и по $4$ — двойку не собрать. Значит, стоячих плиток нет ни в одном столбце, то есть нет вообще, и каждый столбец разбит на куски $3 + 3$. Тогда весь прямоугольник распадается на две горизонтальные полосы высоты $3$, и каждую полосу заполняют лежачие плитки ширины $4$. Но ширина полосы равна $14$, а $14$ на $4$ не делится. Противоречие: укладки $14 \times 6$ не существует.

Ищем следующий кандидат. Площадь $14 \cdot n$ делится на $12$ ровно тогда, когда $7n$ делится на $6$, то есть когда $n$ кратно $6$. После $n = 6$ идёт $n = 12$ — и такой прямоугольник уже режется: разобьём ширину на четыре столбца, $14 = 4 + 4 + 3 + 3$.

Доказательство

Ответ собирается из двух частей — запрета и примера. Запрет: вторая сторона кратна $6$, а вариант $n = 6$ невозможен по рассуждению со столбцом. Пример: укладка $14 \times 12$ предъявлена на чертеже. Значит, наименьшая площадь

$$S = 14 \cdot 12 = 168.$$

Ответ: $168$.

Что и требовалось — понять

Попробуйте сами

Теперь сами: сторона прямоугольника равна $8$, плитки те же, $3 \times 4$. Какова наименьшая площадь? Проверьте и делимость, и укладку.

Показать ответ

Площадь $8n$ делится на $12$, когда $n$ кратно $3$. Первый кандидат $n = 3$ сразу удаётся: прямоугольник $8 \times 3$ складывается из двух лежачих плиток. Наименьшая площадь: $24$ — здесь, в отличие от исходной задачи, первый же кандидат по делимости подтверждается укладкой.