Задание №180828: Командная олимпиада 2021

Ответ: 10002 − 2 ⋅ 999.
Решение.
Утверждение.Есликдоске𝑚×𝑛применитьуказаннуюоперациюнесколькораз,тооста-
нутсянеодноклеточныепрямоугольникисуммарнойплощадьюхотябы2(min(𝑚,𝑛) − 1)
клеток.
Доказательство.
Заметим, что ни один прямоугольник, кроме, собственно, 1×1 нельзя с помощью разре-
шенных действий разрезать на 1 × 1 без остатка. Таким образом, для всех неодноклеточ-
ных прямоугльников будет потеряно хотя бы 2 клетки.
Теперьдокажемутверждениепоиндукции:Базаиндукции:прямоугольникисоднимиз
3

измерений равным 1. Заметим, что для 1 × 1 утверждение верно, а в остальных случаях
для прямоугольника 1 × 𝑎 мы теряем даже не 0, а 𝑘 площади.
Переход:пустьдлявсехпрямоугольников,строгоменьшихискомогоутверждениеверно,
докажем для искомого.
Разобьём доску на три меньших первым ходом, для каждой напишем эту оценку и про-
суммируем: пусть у нас доска 𝑚 × 𝑛 разбилась на три прямоугольника:
• 𝑚 × 𝑘,
• 𝑙 × (𝑛 − 𝑘),
• (𝑚 − 𝑙) × (𝑛 − 𝑘).
Случай 1. Пусть 𝑚 ⩾ 𝑛.
Тогдамыполучимнеодноклеточныхпрямоугольниковсуммарнойплощадьюнеменьше
2(min(𝑚,𝑘) − 1) + 2(min(𝑙,𝑛 − 𝑘) − 1) + 2(min(𝑚 − 𝑙,𝑛 − 𝑘) − 1) =
= (2𝑘 − 2) + 2(min(𝑙,𝑛 − 𝑘) − 1) + 2(min(𝑚 − 𝑙,𝑛 − 𝑘) − 1).
Заметим,чтоеслихотябыодинизоставшихсяминимумовравен𝑛−𝑘,исредиэтихдвух
прямоугольников нет 1 × 1, то вся сумма не меньше, чем
2𝑘 − 2 + 2(𝑛 − 𝑘) − 2 + 2 = 2𝑛 − 2.
Если же один из них это прямоугольник 1 × 1, то 𝑛 − 𝑘 = 1, то вся сумма не меньше, чем
2𝑘 − 2 + 𝑚 − 1 = 2(𝑛 − 1) − 2 + 𝑚 − 1 ⩾ 2𝑛 − 2.
А если оба не равны, то сумма равняется
(2𝑘 − 2) + (2𝑙 − 2) + (2(𝑚 − 𝑙) − 2) = 2𝑘 + 2𝑚 − 6.
Это меньше 2𝑛 − 2 только если 𝑚 = 𝑛 и 𝑘 = 1 — но вот только для 𝑘 = 1 прямоугольник
𝑚×𝑘 теряет не 0, а 𝑚 клеток, что дает нам 3𝑚−4 ⩾ 2𝑛−2 для всех 𝑚 ⩾ 2, а значит и для
всех 𝑚, рассматриваемых в переходе.
Случай 2. Пусть 𝑚 < 𝑛.
Если 𝑘 ⩽ 𝑚, то этот случай рассматривается аналогичным образом. Если же 𝑘 > 𝑚, то
мы получаем цепочку неравенств 𝑛 > 𝑘 > 𝑚 > 𝑙. Тогда мы получим неодноклеточных
прямоугольников суммарной площадью не меньше
2(min(𝑚,𝑘) − 1) + 2(min(𝑙,𝑛 − 𝑘) − 1) + 2(min(𝑚 − 𝑙,𝑛 − 𝑘) − 1) =
= 2𝑚 − 2 + 2(min(𝑙,𝑛 − 𝑘) − 1) + 2(min(𝑚 − 𝑙,𝑛 − 𝑘) − 1) ⩾ 2𝑚 − 2
Для четных 𝑚 и 𝑛 (в частности для 𝑚 = 𝑛 = 1000), оценка точная — для того, чтобы
потерять не более, чем 2 ⋅ (𝑚𝑖𝑛(𝑚,𝑛) − 1) площади, надо каждым ходом от оставшегося
4

«большого»(состоронами,большими2)прямоугольникаотрезатьпрямоугольник2×𝑛,а
отостатка—ещёодинсостороной2.Такмыпорежемвсёнапрямоугольникисостороной
2, а из каждого того куска отрезая по два одноклеточных,можно оставить лишь одну не
разрезанную доминошку.