Районная олимпиада, 2003-2004 учебный год, 9 класс

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

Комментарий/решение

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

Примерно так будет выглядеть таблица.

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

Ответ: 1683

Небольшое уточнение, при ориентации таблицы, как в приведенном решении, левый столбец и нижняя строка состоят из 1, а любое другое число равно сумме чисел слева. снизу и слева-снизу по диагонали.