Раскраски

Пример.

Пронумеруем спичечные столбцы и строчки таблицы от 1 до . Сначала уберём все спички на границе. Затем уберём по 2 верхние спички 2 -го, 4 -го, . . -го столбцов. Затем во 2 -й строчке уберём спичек ( отрезок длины 2 ) так, чтобы остались спички по краям. Затем уберём по 2 спички из 3 -го, 5 -го, ..., -го столбцов так, чтобы сверху осталось по одной спичке в этих столбцах. Далее уберём все спички 3 -й строчки. Затем уберём по 2 верхние спички чётных столбцов, затем средних спичек 4 -й строчки, затем верхние спички внечётных столбцах, а затем все спички 5-й строки. Будем дальше продолжать этот алгоритм, несложно убедиться, что останутся только крайние спички в нечётных столбцах (не считая 1 и ) и чётных строках, в итоге .

Оценка

Первый способ.

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

Таким образом, в конце останется хотя бы по одной покрашенной спичке в каждом из выделенных квадратиков.

Второй способ.

Покрасим синим все спички, которые не лежат на границе квадрата . Всего покрашено горизонтальных и вертикальных рядов по спичек. Итого, у нас синих спичек.

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

синих спичек.