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

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

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

1 9 28 64 152

1 7 12 24 64

1 5 0 12 28

1 3 5 7 9

1 1 1 1 1

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

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

Ответ: 152.