СПбГУ 2026, 8-9 классы, задача 3

Сложная
Комбинаторика
Источник:
Олимпиады школьников СПбГУ, Отборочный этап, 2026, 8–9 классы

( баллов) Король ходит по клетчатой доске . Он начинает в левом нижнем углу, а должен закончить в правом верхнем, смещаясь за один ход ровно на одну клеточку. Ему запрещено возвращаться на ту клеточку, где он уже был до этого, а также переходить в более левые столбцы. Другими словами, король может ходить только вверх, вниз, вправо, вправо-вверх и вправо-вниз. Сколько у короля есть способов пройти свой маршрут? В ответ укажите последние цифры количества способов.

Войдите, чтобы проверять ответы
Ответ

Ответ: .

Решение. Будем находить количество возможных путей от левого нижнего угла доски по столбцам. Легко заметить, что в любую клеточку самого левого столбца доски можно попасть единственным способом (двигаясь снизу вверх).

Теперь предположим, что для -го столбца нам известны количества путей, которыми в каждую из клеток этого столбца можно попасть из левой нижней клетки доски. Из каждой внутренней клетки (то есть из любой, кроме самой нижней и самой верхней) можно пойти тремя путями (вправо, вправо-вверх и вправо-вниз). Из нижней и верхней клеток есть только по два пути (вправо и вправо-вверх или вправо-вниз соответственно). И каждый такой путь даёт единственный способ переместиться в клетку -го столбца из нижней левой клетки доски. Действительно, мы в любую клетку -го столбца попадаем либо напрямую из клетки -го столбца, либо должны продвинуться ещё и вверх или вниз по клеткам -го столбца (а такое продвижение единственно, так как по условию нельзя ходить на уже посещенные клетки).

Следовательно, чтобы получить количество способов пройти от левой нижней клетки доски до какой-либо клетки -го столбца, необходимо вычислить выражение

где — количество способов добраться в -ю клетку -го столбца.

Аккуратный подсчет даст число, оканчивающееся на .

1

Верное решение

20
Максимум: 20

Похожие задачи

СПбГУ 2022, 8–9 классы, задача 11

(40 баллов) Числа от 1 до 600 разбиты на несколько групп. Известно, что если в группе более одного числа, то сумма любых двух чисел из этой группы делится на 6. Какое наименьшее количество групп может быть?
Сложная
Теория чисел
Комбинаторика

СПбГУ 2024, 10–11 классы, задача 6

(40 баллов) На доске написаны числа 1, 2, 3,..., 2023. Раз в минуту к доске подбегает Жора. Он выбирает некоторое натуральное число k, но не обязательно написанное на доске. После этого каждое число на доске, не меньшее k, уменьшает на k. После нескольких операций на доске осталось ровно одно ненуле
Сложная
Комбинаторика

СПбГУ 2025, 8–9 классы, задача 9

(40 баллов) В вершинах правильного 100-угольника расположены целые числа, сумма которых равна 2025. Два игрока по очереди берут себе по одному числу. Первый игрок начинает, выбирая любое число. Со второго хода разрешается брать числа только из вершин, соседних с теми, откуда уже были взяты числа. По
Сложная
Комбинаторика

СПбГУ 2022, 8–9 классы, задача 12

(40 баллов) Пять мальчиков играли в слова: каждый из них написал по 7 различных слов. Оказалось, что у каждого мальчика есть ровно по 2 слова, которые не встречаются ни у одного из остальных мальчиков. Какое наибольшее количество различных слов могли суммарно написать мальчики?
Сложная
Комбинаторика