Олимпиада имени Леонарда Эйлера 2018-2019 учебный год, I тур дистанционного этапа

Кузнечик начинает движение в левой верхней клетке квадрата $10\times 10.$ Он может прыгать на одну клетку вниз или вправо. Кроме того, кузнечик может из самой нижней клетки любого столбца перелететь в самую верхнюю клетку того же столбца, а из самой правой клетки любой строки перелететь в самую левую клетку той же строки. Докажите, что кузнечику понадобится хотя бы 9 перелетов, чтобы побывать на каждой клетке квадрата хотя бы по одному разу.

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

Комментарии от администратора Комментарии от администратора №1.     Не совершая перелета, кузнечик может попасть из клетки $K$, где он находится, только в клетки прямоугольника, где $K$ — левая верхняя клетка. Покрасим красным 10 клеток, лежащих на диагонали квадрата, идущей из правой верхней клетки в левую нижнюю. Прямоугольник, в левом верхнем углу которого находится красная клетка, не содержит других красных клеток. Поэтому, двигаясь только вниз или вправо, кузнечик не сможет попасть из одной красной клетки в другую, не совершив перелета, из чего и вытекает утверждение задачи.

Не совершая перелетов кузнечик может пройти max 19 клеток. Значит, с 8 перелетами он пройдёт max 19 + 8 * 10 = 99 клеток. Так как в квадрате 10 × 10 всего 100 клеток, то кузнечик никак не сможет пройти через все клетки. Значит, минимум понадобится 9 перелетов.

Но нам же хватает 99 прыжков

Я ошибся когда писал, спасибо за замечание