Олимпиада имени Леонарда Эйлера 2016-2017 учебный год, 2 тур регионального этапа

Имеется клетчатая доска размером $2n \times 2n$. Петя поставил на неё ${(n+1)^2}$ фишек. Кот может одним взмахом лапы смахнуть на пол любую одну фишку или две фишки, стоящие в соседних по стороне или углу клетках. За какое наименьшее количество взмахов кот заведомо сможет смахнуть на пол все поставленные Петей фишки? ( С. Берлов, Н. Власова )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. $n^2+n$. Решение. Оценка. Разделим доску на $n^2$ квадратов $2\times 2$. Кот может смахнуть любые две фишки, стоящие в одном квадрате. Пока фишек на доске больше, чем $n^2$, у него есть возможность смахнуть две фишки, то есть он сможет сделать это по крайней мере $n+1$ раз (после $n$ таких действий на доске ещё остаётся $n^2+1 > n^2$ фишек). Смахивая оставшиеся фишки поодиночке, кот обойдётся $(n+1)+(n^2-1) = n^2+n$ взмахами.
Пример. Разобьём доску на квадраты $2 \times 2$. Рассмотрим диагональ, идущую из левого нижнего угла в правый верхний. В левый нижний квадрат поставим 4 фишки, а в остальные, которые пересекает эта диагональ — по 3 фишки так, чтобы левая нижняя клеточка осталась пустой. Во все квадраты выше диагонали поставим по одной фишке в левый верхний угол, во все квадраты ниже — в правый нижний угол. Получим ровно $(n^2-n)+3n+1 = {(n+1)^2}$ фишек. Так как кот не может при данной расстановке фишек одним взмахом сбить фишки из разных квадратов, чтобы сбить все диагональные фишки, необходимо хотя бы $2n$ взмахов, на остальные фишки — $n^2-n$ взмахов, то есть всего — $n^2+n$ взмахов.