Шахматная доска

[wpoms.]

Рассмотрим стандартную `8 xx 8` шахматную доску, состоящую из `64` маленьких квадратов, окрашенных обычным образом, `32` квадрата черные и `32` - белые. Назовем зигзагообразным путем через доску набор из восьми белых квадратов, по одному в каждой горизонтали, которые соприкасаются углами. Сколько всего существует зигзагообразных путей?

@темы: Комбинаторика

Comments

[Trotil]

Задачу можно решить полным перебором.
Начнём стартовать с первой горизонтали. Очевидно, что каждую клетку можно выбрать одним способам. Пометим их как 1,1,1,1. Цифра на клетке означает число способов достижения этой клетки.
Перейдём ко второй диагонали. Отметим число способов достижения каждой белой клетки здесь. Оно будет равно числу "входов", т.е. сумме двух чисел белых клеток или одной клетке. Вторая горизонталь будет помечена как 2,2,2,1. И так далее.

Последняя: 69, 103, 89, 35. Ответ на задачу - сумма этих чисел, т.е. 296.