Эйлер атындағы олимпиада, 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$ взмахов.