На шахматной доске на клетке a1 стоит король, которому необходимо попасть на клетку h8, не попадая на клетки с3, с6, f3, f6. Король может двигаться только вверх или вправо на одну клетку. Сколькими способами это можно сделать?

Обозначим движение вправо как $R$, а движение вверх как $U$. От клетки $a1$ до клетки $h8$ королю нужно сделать ровно 7 ходов вправо и 7 ходов вверх, всего 14 ходов.

Без запретных клеток число путей было бы:

Теперь нужно исключить пути, проходящие через клетки:

Перейдём к координатам:

Запретные клетки:

1. Пути через одну запрещённую клетку

Через $c3$:

от $a1$ до $c3$: 2 вправо и 2 вверх, всего

от $c3$ до $h8$: 5 вправо и 5 вверх, всего

Значит, через $c3$:

Через $c6$:

от $a1$ до $c6$: 2 вправо и 5 вверх,

от $c6$ до $h8$: 5 вправо и 2 вверх,

Итого:

Аналогично через $f3$ тоже будет:

Через $f6$:

от $a1$ до $f6$: 5 вправо и 5 вверх,

от $f6$ до $h8$: 2 вправо и 2 вверх,

Итого:

Суммарно путей, проходящих хотя бы через одну запрещённую клетку, если пока не учитывать пересечения:

Но так мы некоторые пути вычли дважды.

2. Пути через пары запрещённых клеток

Король двигается только вверх и вправо, поэтому через две клетки он может пройти только если одна находится левее и ниже другой.

Возможные пары:

Пары $c6$ и $f3$ несовместимы: из одной в другую нельзя попасть только вверх и вправо.

Посчитаем.

Через $c3$ и $c6$:

Через $c3$ и $f3$:

Через $c3$ и $f6$:

Через $c6$ и $f6$:

Через $f3$ и $f6$: