Комбинаторика на Питергоре

Оценка.

Будем говорить, что выполнили операцию в клетке, если перекрасили все 99 клеток в строке или столбце кроме данной. Пусть были операции над строками в клетках и над столбцами .

Отметим два факта:

1.

Количество операций четно, ведь операция меняет четность числа черных клеток, тогда достаточно показать, что .

2.

Порядок выполнения операций не влияет на конечный результат перекрашивания.

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

Рассмотрим несколько случаев:

1.

Тогда клеток НЕ находящихся в столбцах и строках, где были операции II-го или III-го типа , а любая операция I-го типа перекрашивает не более двух клеток, тогда всего ходов хотя бы

2.

После выполнения операций II-го типа останется ровно 100 белых клеток. , значит, операций III-го типа нет, тогда для перекрашивания белых клеток понадобиться хотя бы 50 операций I-го типа. Получаем, что всего операций не меньше, чем .

3.

После операций II-го типа останется ровно 100 белых клеток, причём по одной в каждой строке. После выполнения операций III-го типа белых клеток останется хотя бы (так как в каждом из q столбцов перекрашивается по 99 клеток, все они чёрные, кроме, может быть, 100 белых клеток, тогда после применения операции белыми станут хотя бы ). Тогда потребуется еще хотя бы ходов, значит, всего шагов не менее

4.

: — нечётное.

Этот случай невозможен по чётности количества ходов.

Случаи для аналогичны случаям для .

_________________________________________________________________________________________________________________________________________________________________________________

Пример.

Выполним операцию III-го типа ко всем клеткам из первой строки. Это 100 ходов. Далее применим операцию I-го типа к парам из клеток первой строки (на пары разобьем последовательно , то есть 1-ая и 2-ая клетки, 3-яя и 4-ая, , 99-ая и 100-ая). Это ещё ходов. Итого 200.