Задача 4. Энтомолог Вася и кузнечики

Где может сидеть кузнечик

Назовём домом кузнечика клетку, в которой он живёт в начале: у первого — клетка $1$, у второго — клетка $2$, …, у десятого — клетка $10$.

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

Ещё одно наблюдение понадобится дальше. Посмотрим сразу после хода кузнечиков на любого кузнечика, который не дома. Перед прыжком он тоже был не дома (кто дома, тот не прыгает и остаётся дома), значит, он прыгнул влево — из клетки не правее $100$, ведь полоска кончается клеткой $100$. Значит, он сидит не правее клетки $99$. А кто дома, сидит в одной из клеток $1$–$10$. Итак, перед каждым ходом Васи все кузнечики сидят не правее клетки $99$.

Одно число на всю игру

Сложим номера клеток, где сидят кузнечики; если в клетке сидят несколько, её номер берём столько раз, сколько их там. Обозначим эту сумму $S$. В начале $S=1+2+\ldots+10=55$.

Если кузнечики сидят по одному в клетках $50,\ 51,\ \ldots,\ 59$ — в любом порядке, — то $S=50+51+\ldots+59=545$. Поэтому достаточно доказать, что ни в какой момент игры $S$ не равна $545$.

Как $S$ меняется за один раунд — ход Васи и прыжок кузнечиков? Вася переносит кузнечика на $d$ клеток вправо, $1\le d\le 6$: номер его клетки, а с ним и $S$, увеличивается на $d$. Потом прыгают $J$ кузнечиков, номер клетки каждого уменьшается на $1$, и $S$ уменьшается на $J$. За раунд $S$ меняется на $d-J$. Например, если Вася перенёс кузнечика на $3$ клетки, а прыгнули $5$ кузнечиков, сумма уменьшилась на $2$.

Когда сумма не растёт

Пусть после какого-то раунда дома не больше $4$ кузнечиков, то есть не дома хотя бы $6$. Как в шаге 1, каждый из них в этом раунде прыгнул: кто дома, тот не прыгает и дома остаётся. Значит, прыгнули хотя бы шестеро: $J\ge 6$.

А Вася в этом раунде прибавил $d\le 6$. Значит, $d-J\le 0$: если после раунда дома не больше четырёх кузнечиков, то за этот раунд сумма $S$ не увеличилась.

Когда дома хотя бы пятеро, сумма не больше 535

Возьмём момент перед ходом Васи, когда дома сидят хотя бы $5$ кузнечиков, и выберем пятерых из них. Они сидят в своих домах — в пяти разных клетках из $1$–$10$, — поэтому сумма их номеров клеток не больше суммы пяти самых больших номеров: $6+7+8+9+10=40$.

Каждый из остальных пяти кузнечиков по шагу 1 сидит не правее клетки $99$, так что вместе они дают не больше $5\cdot 99=495$.

Значит, в такой момент $S\le 40+495=535$.

Сумма никогда не дотягивается до 545

Возьмём любой момент игры перед ходом Васи. Найдём последний до него момент перед ходом Васи, когда дома сидели хотя бы пятеро, и назовём его $X$. Такой момент есть: в самом начале дома все десять. Может оказаться, что $X$ — это и есть наш момент.

• В момент $X$ по шагу 4 $S\le 535$.
• Каждый раунд после $X$ — начиная с того, который начался в момент $X$, — закончился так, что дома было не больше четырёх кузнечиков: иначе $X$ был бы позже. По шагу 3 ни в одном из этих раундов сумма не выросла, поэтому в нашем моменте $S$ не больше, чем в момент $X$.

Значит, перед каждым ходом Васи $S\le 535$. Кузнечики могли бы оказаться собранными только в одном из двух видов моментов:

• после хода кузнечиков, то есть перед следующим ходом Васи, — там $S\le 535$;
• сразу после хода Васи — там $S$ больше, чем перед этим ходом, не более чем на $6$, то есть $S\le 535+6=541$.

И $535$, и $541$ меньше $545$. Поэтому ни в какой момент кузнечики не сидят по одному в клетках $50$–$59$: Вася не сможет их собрать.

Где пригодились все условия

Оценка проходит впритык, и каждое условие в ней работает.

• Клетка $99$, а не $100$. Если оценить каждого кузнечика не дома клеткой $100$, выйдет $40+5\cdot 100=540$, а после хода Васи $546$ — больше $545$, и доказательство не сработает. Важно, что перед ходом Васи кузнечик не дома только что прыгнул.
• Длина полоски. На полоске $1\times 101$ та же оценка тоже дала бы $546$ и ничего бы не запрещала. А на полоске $1\times 126$ кузнечиков действительно можно собрать: компьютер нашёл такую игру — её можно посмотреть в модели, в разделе «За пределами условия» ($335$ ходов).
• Шаг не больше $6$. Из-за него при шести кузнечиках не дома сумма не растёт, а в шаге 4 нужно, чтобы дома было хотя бы $10-6+1=5$ кузнечиков.

Второй вариант

Во втором варианте $8$ лягушек живут в клетках $1$–$8$ полоски $1\times 150$, Петя переносит одну лягушку не дальше чем на $5$ клеток, цель — клетки $75$–$82$. Рассуждение то же, меняются только числа.

• Лягушка не бывает левее своего дома, а перед ходом Пети лягушка не дома только что прыгнула и сидит не правее клетки $149$.
• Сумма номеров клеток $S$ в начале равна $1+2+\ldots+8=36$, для цели нужно $75+76+\ldots+82=628$. За раунд $S$ меняется на $d-J$, где $d\le 5$.
• Если после раунда дома не больше трёх лягушек, то не дома хотя бы $5$, все они в этом раунде прыгнули, и $S$ не выросла.
• Если дома хотя бы четыре лягушки, то четыре из них дают не больше $5+6+7+8=26$, а остальные четыре — не больше $4\cdot 149=596$: $S\le 622$.
• Последний момент $X$ перед ходом Пети, когда дома хотя бы четыре лягушки, существует (это хотя бы начало игры); в нём $S\le 622$, а каждый следующий раунд кончается моментом, когда дома не больше трёх лягушек, — сумма в них не росла.

Значит, перед каждым ходом Пети $S\le 622$, а сразу после хода $S\le 622+5=627$. Обе суммы меньше $628$, поэтому Петя не сможет собрать лягушек.

Здесь запас всего $1$: если оценить лягушек не дома клеткой $150$, получится $26+4\cdot 150+5=631$ — больше $628$. Без наблюдения «перед ходом Пети лягушка не дома только что прыгнула» доказательство не сработало бы. А на длинной полоске $1\times 185$ компьютер собирает лягушек за $473$ хода — это видно в модели («2 вариант», раздел «За пределами условия»).