ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 60449
Темы:    [ Числа Каталана ]
[ Мощность множества. Взаимно-однозначные отображения ]
Сложность: 3+
Классы: 8,9,10,11
Название задачи: Маршруты ладьи.
В корзину
Прислать комментарий

Условие

Рассмотрим шахматную доску n×n. Требуется провести ладью из левого нижнего угла в правый верхний. Двигаться можно только вверх и вправо, не заходя при этом на клетки главной диагонали и ниже нее. (Ладья оказывается на главной диагонали только в начальный и в конечный моменты времени.) Сколько у ладьи существует таких маршрутов?


Подсказка

Установите соответствие между всеми такими маршрутами ладьи и последовательностями чисел из задачи 60447.


Решение

Пусть первый ход ладья делает вверх, тогда последний – вправо. Кроме этого, она должна сделать  n – 1  ход вверх и столько же – вправо. Каждому ходу вверх поставим в соответствие единицу, а ходу вправо – минус единицу. Мы получим последовательность из  2n – 2  чисел, удовлетворяющую условиям задачи 60447. Обратно, по каждой такой последовательности можно построить маршрут ладьи в верхней части доски.


Ответ

2Cn–1.

Источники и прецеденты использования

книга
Автор Алфутова Н.Б., Устинов А.В.
Год издания 2002
Название Алгебра и теория чисел
Издательство МЦНМО
Издание 1
глава
Номер 2
Название Комбинаторика
Тема Комбинаторика
параграф
Номер 5
Название Числа Каталана
Тема Классическая комбинаторика
задача
Номер 02.115

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .