Индукция в комбинаторике

Рассмотрим конечную ситуацию и переформулируем задачу: пусть клетки, которые так и остались пустыми изначально закрашены, а остальные клетки пустые. За один ход Арсений берёт четыре клеточки, образующие вершины прямоугольника, стороны которого параллельны сторонам квадратика, три из которых закрашены, и закрашивает оставшуюся. В конце он должен закрасить весь исходный квадрат (в частности, делая действия в одном порядке). Тогда нас интересует минимальное количество изначально закрашенных клеток.

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

Допустим, в одной из этих строк и в одном из столбцов есть закрашенная клетка снаружи квадрата. Тогда возьмём их столбец и строку, получим искомый набор из строк и столбцов. Мы добавили хотя бы две клетки, ясно, что этот можно восстановить целиком.

Тогда пусть в этих строках больше нет изначально закрашенных клеток. Если их нет и в продолжении столбцов, то мы не можем восстановить весь квадрат (поскольку для клеток в продолжении строк нужно брать прямоугольник с противоположной вершиной в продолжении столбцов). Рассмотрим оставшиеся верхние строки (которых В каждой из них точно есть изначально закрашенные клетки (иначе нельзя восстановить данную строку). Если есть строка, где одна закрашенная клетка в одном из первых столбцов, а другая — нет, то мы победили: просто возьмём эту строку и столбец из оставшихся где есть её клетка. Тогда мы можем восстановить эту строку, пользуясь квадратом, а столбец восстановим, пользуясь верхней строкой. Снова мы добавили клетки.

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

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

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