Математикадан Эйлер олимпиадасы, 2018-2019 оқу жылы, Дистанциялық кезеңнің 1-ші туры

Шегіртке қозғалысты $10\times 10$ тор тақтаның жоғарғы сол шаршысынан бастайды. Ол бір шаршы төмен немесе бір шаршы оңға секіре алады. Сонымен қатар, шегіртке кез келген бағанның ең төменгі шаршысынан осы бағанның ең жоғары шаршысына ұшып бара алады; және кез келген қатардың ең оң шаршысынан осы қатардың ең сол шаршысына ұшып бара алады. Шегірткеге тақтаның әр шаршысында кемінде бір реттен болып шығу үшін, оған кемінде 9~рет ұшу керек екенін дәлелдеңіздер.

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

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

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

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

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