Задача
Рассмотрим шахматную доску n×n. Требуется провести ладью из левого нижнего угла в правый верхний. Двигаться можно только вверх и вправо, не заходя при этом на клетки главной диагонали и ниже нее. (Ладья оказывается на главной диагонали только в начальный и в конечный моменты времени.) Сколько у ладьи существует таких маршрутов?
Решение
Пусть первый ход ладья делает вверх, тогда последний – вправо. Кроме этого, она должна сделать n – 1 ход вверх и столько же – вправо. Каждому ходу вверх поставим в соответствие единицу, а ходу вправо – минус единицу. Мы получим последовательность из 2n – 2 чисел, удовлетворяющую условиям задачи 60447. Обратно, по каждой такой последовательности можно построить маршрут ладьи в верхней части доски.
Ответ
2Cn–1.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь