Путешествие короля

В левом нижнем углу шахматной доски 6x6 стоит король. За один ход он может передвинуться либо на одну клетку вправо, либо на одну клетку вверх, либо на одну клетку по диагонали - вправо и вверх. Сколькими разными путями король пройти в правый верхний угол доски? 

Ответ: Составим таблицу, заполняющую левый нижний угол доски, причем в каждой клетке напишем число, равное количеству допустимых путей, которыми король может дойти до этой клетки из левого нижнего угла. Левый столбец и нижняя строка заполнены единицами. В остальных клетках ставим сумму чисел, стоящих в трех соседних клетках - снизу, слева и по диагонали снизу слева. Так, начиная с левого нижнего угла, достраиваем таблицу до правого верхнего и получаем ответ 1683. Таково число различных маршрутов.

1 11 61 231 681 1683
1 9 41 129 321 681
1 7 25 63 129 231
1 5 13 25 41 61
1 3 5 7 9 11
1 1 1 1 1 1

 

Ваша оценка: Нет Средняя: 3.7 (14 оценки)


Комментарии

Интересный факт. А если рассмотреть классическую шахматную доску 8x8, то у короля есть 48639 возможных маршрутов движения.