2018-12-08
На поле E1 шахматной доски стоит шашка. Сколько существует различных маршрутов, по которым она сможет пройти в дамки?
(Напомним, что шашка может ходить вперед по диагонали на соседнюю клетку и превращается в дамку, если достигает восьмой горизонтали).
Решение:
Так как шашка ходит по диагонали, то она все время остается на клетках одного цвета (в данном случае - черного). Пусть некоторая черная клетка $x$ находится не на первой горизонтали. Если при этом она находится на крайней вертикали, то пойти на эту клетку можно только с одной клетки $y$, поэтому маршрутов от клетки E1 до клетки $x$ существует столько же, сколько от E1 до клетки $y$. Если клетка $x$ находится не на крайней вертикали, то пойти на нее можно из двух клеток, причем если к этим клеткам от E1 приводило $m$ и $n$ маршрутов, то к клетке $x$ от E1 ведет $m + n$ маршрутов.
Двигаясь последовательно от второй до восьмой горизонтали, поставим в каждую из клеток, в которые может попасть шашка, число, равное количеству приводящих в нее маршрутов (см. рис.). Таким образом, количество маршрутов, приводящих к клеткам восьмой горизонтали: 20 + 35 + 34 + 14 = 103.
Ответ: 103.