Задача 79614

Темы:    [ Задачи с ограничениями ] [ Числовые таблицы и их свойства ] [ Обход графов ]

Сложность: 3+ Классы: 9

Условие

В квадратной таблице из 9×9 клеток отмечены 9 клеток, лежащие на пересечении второй, пятой и восьмой строк со вторым, пятым и восьмым столбцами. Сколькими путями можно из левой нижней клетки попасть в правую верхнюю, двигаясь только по неотмеченным клеткам вверх или вправо?

Решение

Пусть a_i,j – число путей из левой нижней клетки в клетку (i, j), не проходящих по отмеченным клеткам. Заметим, что если клетка  (i, j)  не отмечена, то   a_i,j = a_i–1,j + a_i,j–1   (а если отмечена, то  a_i,j = 0).  Теперь несложно посчитать эти числа для каждой клетки доски (см. рисунок).

Ответ

678 путями.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	55
Год	1992
вариант
Класс	9
задача
Номер	4