Версия для печати
Убрать все задачи

---

Докажите, что числа Каталана удовлетворяют рекуррентному соотношению   C_n = C₀C_n–1 + C₁C_n–2 + ... + C_n–1C₀.
Определение чисел Каталана C_n смотри в справочнике.

---

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

Страница: << 16 17 18 19 20 21 22 [Всего задач: 110]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 60448  (#02.114)

Темы:   [ Числа Каталана ] [ Мощность множества. Взаимно-однозначные отображения ]

Сложность: 4 Классы: 8,9,10,11

Сколько существует способов разрезать выпуклый (n+2)-угольник диагоналями на треугольники?

Решение

  Построим взаимно однозначное соответствие между триангуляциями многоугольника и расстановками скобок в произведении x₀x₁...x_n. Выделим одну из сторон AB  (n+2)-угольника; все остальные стороны занумеруем по порядку символами x₀, x₁, ..., x_n. Каждая проведенная диагональ "отсекает" от многоугольника последовательность сторон, не содержащую AB. Соответствующую часть произведения x₀x₁...x_n заключим в скобки. Всего будет расставлена  n – 1  пара скобок.
  Например, разрезанию шестиугольника на рисунке соответствует расстановка скобок (x₀((x₁x₂)x₃))x₄.

  Легко видеть, что так получаются все возможные расстановки скобок в произведении.

Ответ

C_n.

Прислать комментарий

---

Задача 60449  (#02.115)  [Маршруты ладьи]

Темы:   [ Числа Каталана ] [ Мощность множества. Взаимно-однозначные отображения ]

Сложность: 3+ Классы: 8,9,10,11

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

Подсказка

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

Решение

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

Ответ

2C_n–1.

Прислать комментарий

---

Задача 60450  (#02.116)  [Очередь в кассу]

Темы:   [ Числа Каталана ] [ Мощность множества. Взаимно-однозначные отображения ]

Сложность: 3+ Классы: 8,9,10,11

Билеты стоят 50 центов, и 2n покупателей стоят в очереди в кассу. Половина из них имеет по одному доллару, остальные – по 50 центов. Кассир начинает продажу билетов, не имея денег. Сколько существует различных порядков в очереди, таких, что кассир всегда может дать сдачу?

Подсказка

Поставив каждому покупателю с 50 центами в соответствие единицу, а покупателю с долларом – минус единицу, мы получим последовательность, удовлетворяющую условиям задачи 60447.

Ответ

C_n.

Прислать комментарий

---

Задача 60451  (#02.117)  [Формула для чисел Каталана]

Темы:   [ Числа Каталана ] [ Принцип крайнего (прочее) ] [ Комбинаторика орбит ]

Сложность: 4+ Классы: 8,9,10,11

  а) Пусть  {a₁, a₂,..., a_n}  – последовательность целых чисел, сумма которых равна 1. Докажите, что ровно у одного из ее циклических сдвигов
{a₁, a₂, ..., a_n},  {a₂, ..., a_n, a₁},  ...,  {a_n, a₁, ..., a_n–1}  все частичные суммы (от начала до произвольного элемента) положительны.

  б) Выведите отсюда равенства:      где  (4n – 2)!!!! = 2·6·10·...(4n – 2)  – произведение, в котором участвует каждое четвёртое число.
  Определение чисел Каталана C_n смотри в справочнике.

Решение

   а) Назовем весом последовательности такое число k, что частичные суммы  s₁ = a₁,  ...,  s_k = a₁ + ... + a_k  положительны, а  s_k+1 ≤ 0  (если  k < n).  Рассмотрим циклический сдвиг, после которого образуется последовательность  {b₁, ..., b_n} наибольшего веса. Докажем, что этот вес равен n. Пусть это не так, тогда рассмотрим наиболее "длинную" неположительную частичную сумму  b₁ + ... + b_k.  Тогда все суммы  b_k+1,  b_k+1 + b_k+2,  ...,  b_k+1 + ... + b_n  положительны. Это значит, что переставив  b_k+1, ..., b_n  в начало последовательности, мы увеличим ее вес. Противоречие.
  Пусть есть два разных циклических сдвига, удовлетворяющих условию. Например, и у  {a₁, a₂, ..., a_n}  и у  {a_m, ..., a_n, a₁, ..., a_m–1}  все частичные суммы положительны. Тогда числа  a₁ + ... + a_m–1  и  a_m + ... + a_n  натуральные, а их сумма равна 1. Противоречие.

  б) Количество последовательностей из  n + 1  единиц и n минус единиц равно     Из а) следует, что количество таких последовательностей, у которых все частичные суммы положительны, равно     Отбросив у каждой первый член (который равен 1), мы получим все последовательности из задачи 60447, а их C_n.
  Последнее равенство следует из того, что   (2n)! = 1·3·...·(2n – 1)·2·4·...·2n = 2·6·...·(4n – 2)·1·2·...·n = (4n – 2)!!!!·n!.

Прислать комментарий

---

Задача 60452  (#02.118)  [Рекуррентное соотношение для чисел Каталана]

Тема:   [ Числа Каталана ]

Сложность: 3+ Классы: 8,9,10,11

Докажите, что числа Каталана удовлетворяют рекуррентному соотношению   C_n = C₀C_n–1 + C₁C_n–2 + ... + C_n–1C₀.
Определение чисел Каталана C_n смотри в справочнике.

Подсказка

Рассмотрите в произведении  x₀x₁...x_n  то умножение, которое делается последним.

Прислать комментарий

---

Страница: << 16 17 18 19 20 21 22 [Всего задач: 110]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями