Задача 2. Дырки на диагонали

Когда дырка оказывается внутри детали

Пронумеруем столбцы слева направо, а строки снизу вверх числами от $1$ до $9$; клетку в столбце $a$ и строке $b$ обозначим $(a,\,b)$. Диагональ из левого нижнего угла в правый верхний проходит через клетки $(1,\,1),\ (2,\,2),\ \ldots,\ (9,\,9)$ — назовём их клетками диагонали. Соседние клетки диагонали касаются друг друга только уголком, и в каждом таком уголке просверлена дырка — всего $8$ дырок.

В каждом узле сетки сходятся четыре клетки. Узел лежит внутри прямоугольной детали, если все четыре клетки вокруг него принадлежат этой детали. Если хотя бы одна из них чужая, через узел проходит распил, и узел лежит на границе детали.

• Пусть дырка оказалась внутри детали. Тогда в детали все четыре клетки вокруг дырки, а среди них две клетки диагонали.

• Пусть, наоборот, в детали есть две клетки диагонали, $(a,\,a)$ и $(b,\,b)$, где $a<b$. Прямоугольник, в котором есть обе эти клетки, занимает все столбцы с $a$-го по $b$-й и все строки с $a$-й по $b$-ю. Значит, в нём есть квадрат $2\times 2$ из клеток $(a,\,a)$, $(a+1,\,a)$, $(a,\,a+1)$, $(a+1,\,a+1)$, а в центре этого квадрата — дырка. Она внутри детали.

Вывод: деталь не содержит дырок внутри ровно тогда, когда в ней не больше одной клетки диагонали. Думать про точки-дырки неудобно, а клетки легко считать — дальше пользуемся этим правилом.

Сколько деталей «занимает» диагональ

Клеток диагонали $9$, и по шагу 1 никакие две из них не могут попасть в одну деталь. Значит, $9$ деталей содержат ровно по одной клетке диагонали, а остальные $11-9=2$ детали диагональ не задевают.

Мешает ли это сделать все площади разными? Если $11$ площадей разные, то самые маленькие из возможных — $1,\,2,\,\ldots,\,11$, и их сумма

А сумма площадей всех деталей равна площади доски: $9\cdot 9=81$. Так как $66<81$, подсчёт ничего не запрещает — остаётся запас в $15$ клеток. Значит, стоит искать пример.

Одно наблюдение, чтобы не запутаться: деталь с клеткой диагонали не обязана быть узкой полоской. Если клетка диагонали стоит в углу прямоугольника, а остальные его клетки лежат по одну сторону от диагонали, то других клеток диагонали в нём нет — и он может быть большим.

Строим пример: полоски и два больших прямоугольника

Полоска шириной в одну клетку — это кусок одной строки или одного столбца. Диагональ пересекает её не больше чем в одной клетке, поэтому любая полоска годится. Площадь полоски равна её длине. Возьмём девять полосок длиной $1,\,2,\,\ldots,\,9$: площади у них уже разные, а вместе они займут

клеток. На две оставшиеся детали приходится $81-45=36$ клеток. Их площади должны быть больше $9$ и разные, например $16$ и $20$, ведь $16+20=36$. Эти большие прямоугольники поставим так, чтобы клетка диагонали была у них в углу (шаг 2).

Выпиливаем детали по кругу, от края доски к середине, и каждую следующую полоску делаем на клетку короче:

• правый столбец целиком — полоска $9$;

• две верхние строки без правой клетки — прямоугольник $8\times 2$, площадь $16$; клетка диагонали $(8,\,8)$ — его правый нижний угол;

• строка 7 без правой клетки — полоска $8$; строка 6, столбцы 2–8 — полоска $7$; строка 5, столбцы 3–8 — полоска $6$;

• столбец 1, строки 2–6 — полоска $5$; столбец 2, строки 2–5 — полоска $4$; столбец 3, строки 2–4 — полоска $3$;

• в нижней строке — клетки $(2,\,1)$ и $(3,\,1)$, полоска $2$, и угловая клетка $(1,\,1)$, площадь $1$;

• осталось место в столбцах 4–8 и строках 1–4: это прямоугольник $5\times 4$, площадь $20$, а клетка диагонали $(4,\,4)$ — его левый верхний угол.

Получилась «спираль» из полосок $9,\,8,\,7,\,\ldots,\,1$ и два прямоугольника — $16$ и $20$ (рисунок).

Проверяем пример

Проверим все условия задачи по рисунку.

• Деталей $11$, все они прямоугольники, и распилы идут по линиям сетки.

• Площади $1,\,2,\,3,\,4,\,5,\,6,\,7,\,8,\,9,\,16,\,20$ — все разные. Их сумма $45+16+20=81$ равна площади доски, и детали не налезают друг на друга: доска распилена целиком.

• Клетки диагонали оказались в разных деталях: $(1,\,1)$ — отдельная клетка; $(2,\,2)$ и $(3,\,3)$ — в полосках $4$ и $3$; $(4,\,4)$ — угол прямоугольника $20$; $(5,\,5)$, $(6,\,6)$ и $(7,\,7)$ — в полосках $6$, $7$ и $8$; $(8,\,8)$ — угол прямоугольника $16$; $(9,\,9)$ — в правом столбце. В полосках $5$ и $2$ клеток диагонали нет.

Значит, в каждой детали не больше одной клетки диагонали, и по шагу 1 ни одна дырка не оказалась внутри детали: все $8$ дырок лежат на распилах.

Итак, доску можно распилить на $11$ деталей так, что все площади разные. Две детали равной площади найдутся не обязательно.

Второй вариант

Во втором варианте доска $10\times 10$, дырок $9$, а диагональ идёт из левого верхнего угла в правый нижний. Нумеруем столбцы слева направо и строки снизу вверх, как раньше; клетки диагонали теперь $(1,\,10),\ (2,\,9),\ \ldots,\ (10,\,1)$. Правило шага 1 не меняется: если в детали две клетки диагонали, $(a,\,11-a)$ и $(b,\,11-b)$ при $a<b$, то в ней есть квадрат $2\times 2$ из столбцов $a$, $a+1$ и строк $10-a$, $11-a$ с дыркой в центре; а дырка внутри детали — это снова две клетки диагонали вокруг неё. Клеток диагонали $10$, поэтому $10$ деталей содержат по одной клетке диагонали и только одна деталь — ни одной. Подсчёт опять не мешает: $1+2+\ldots+11=66<100$.

Пример строится тем же приёмом — полоски и большие прямоугольники, у которых клетка диагонали в углу; спираль теперь идёт от левого края:

• левый столбец целиком — $10$;

• строки 9–10, столбцы 2–10 — прямоугольник $9\times 2$, площадь $18$; клетка диагонали $(2,\,9)$ — его левый нижний угол;

• строка 8, столбцы 2–10 — $9$; строка 7, столбцы 2–8 — $7$; строка 6, столбцы 2–7 — $6$;

• столбцы 9–10, строки 2–7 — прямоугольник $2\times 6$, площадь $12$; клетка диагонали $(9,\,2)$ — его левый нижний угол;

• столбец 8, строки 2–6 — $5$; столбец 7, строки 2–5 — $4$;

• строка 1, столбцы 8–10 — $3$; клетка $(7,\,1)$ — $1$ (единственная деталь без клетки диагонали);

• столбцы 2–6, строки 1–5 — квадрат $5\times 5$, площадь $25$; клетка диагонали $(6,\,5)$ — его правый верхний угол.

Площади $1,\,3,\,4,\,5,\,6,\,7,\,9,\,10,\,12,\,18,\,25$ разные, их сумма $100$ — доска распилена целиком. Клетки диагонали оказались в разных деталях: $(1,\,10)$ — в левом столбце $10$; $(2,\,9)$ — угол прямоугольника $18$; $(3,\,8)$, $(4,\,7)$ и $(5,\,6)$ — в полосках $9$, $7$ и $6$; $(6,\,5)$ — угол квадрата $25$; $(7,\,4)$ и $(8,\,3)$ — в полосках $4$ и $5$; $(9,\,2)$ — угол прямоугольника $12$; $(10,\,1)$ — в полоске $3$. В детали $1$ клеток диагонали нет. Значит, в каждой детали не больше одной клетки диагонали, и по правилу шага 1 ни одна дырка не оказалась внутри детали. Рисунок этого распила — над этим шагом; в модели он открывается кнопкой «Показать пример» при выбранном «2 вариант».

Ответ второго варианта: не обязательно.