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

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