Выбрано 19 задач 
Убрать все задачи
F(x) – возрастающая функция, определённая на отрезке [0, 1]. Известно, что область её значений принадлежит отрезку [0, 1]. Доказать, что, каково бы ни было натуральное n, график функции можно покрыть N прямоугольниками, стороны которых параллельны осям координат так, что площадь каждого равна 1/n². (В прямоугольник мы включаем его внутренние точки и точки его границы.)
Сумма нескольких положительных чисел равна 10, а сумма квадратов этих чисел больше 20. Докажите, что сумма кубов этих чисел больше 40.
Чему равны числа Фибоначчи с отрицательными
номерами F-1, F-2, ..., F-n,...?
В связном графе степени четырёх вершин равны 3, а степени остальных вершин равны 4.
Докажите, что нельзя удалить ребро так, чтобы граф распался на две изоморфные компоненты связности.
Докажите, что точки, симметричные точке пересечения
высот треугольника ABC относительно его сторон, лежат
на описанной окружности.
Двое играющих по очереди увеличивают натуральное число так, чтобы при каждом увеличении разность между новым и старым значениями числа была бы больше нуля, но меньше старого значения. Начальное значение числа равно 2. Выигравшим считается тот, в результате хода которого получится 1987. Кто выигрывает при правильной игре: начинающий или его партнёр?
Некто приобрел
пару кроликов и поместил их в огороженный со всех сторон загон.
Сколько кроликов будет через год, если считать, что каждый месяц
пара дает в качестве приплода новую пару кроликов, которые со
второго месяца жизни также начинают приносить приплод?
а) Есть 128 монет двух различных весов, монет каждого веса поровну. Как на чашечных весах без гирь гарантированно найти две монеты разного веса не более чем за семь взвешиваний?
б) Есть восемь монет двух различных весов, монет каждого веса поровну. Как на чашечных весах без гирь гарантированно найти две монеты разного веса за два взвешивания?
Внутри треугольника ABC взята такая точка P, что
PAB :
PAC =
PCA :
PCB =
PBC :
PBA = x. Докажите, что x = 1.
Cколько существует различных семизначных телефонных номеров (cчитается, что номер начинаться с нуля не может)?
Пусть Oa, Ob и Oc — центры вневписанных
окружностей треугольника ABC. Докажите, что точки A, B и C — основания высот треугольника OaObOc.
Сколько существует ожерелий, составленных из 17 различных бусинок?
На сторонах BC, CA и AB треугольника ABC взяты
точки A1, B1 и C1, причем
AC1 = AB1, BA1 = BC1 и CA1 = CB1.
Докажите, что A1, B1 и C1 — точки касания вписанной
окружности со сторонами.
Некоторый алфавит состоит из 6 букв, которые для передачи по телеграфу кодированы так:
Докажите, что в любом графе
а) сумма степеней всех вершин равна удвоенному числу рёбер (и следовательно, чётна);
б) число вершин нечётной степени чётно.
Докажите, что сторона BC треугольника ABC видна из
центра O вписанной окружности под углом
90o + A/2, а из
центра Oa вневписанной окружности под углом
90o -
A/2.
В языке одного древнего племени было 6 гласных и 8 согласных, причём при составлении слов гласные и согласные непременно чередовались. Сколько слов из девяти букв могло быть в этом языке?
Семнадцать девушек водят хоровод. Сколькими различными способами они могут встать в круг?
а) Пусть {a1, a2,..., an} – последовательность целых чисел, сумма которых равна 1. Докажите, что ровно у одного из ее циклических сдвигов
{a1, a2, ..., an}, {a2, ..., an, a1}, ..., {an, a1, ..., an–1} все частичные суммы (от начала до произвольного элемента) положительны.
б) Выведите отсюда равенства: где (4n – 2)!!!! = 2·6·10·...(4n – 2) – произведение, в котором участвует каждое четвёртое число.
Определение чисел Каталана Cn смотри в
справочнике.
|
Название задачи: Формула для чисел Каталана. |
 |
Условие
а) Пусть {a1, a2,..., an} – последовательность целых чисел, сумма которых равна 1. Докажите, что ровно у одного из ее циклических сдвигов
{a1, a2, ..., an}, {a2, ..., an, a1}, ..., {an, a1, ..., an–1} все частичные суммы (от начала до произвольного элемента) положительны.
б) Выведите отсюда равенства: где (4n – 2)!!!! = 2·6·10·...(4n – 2) – произведение, в котором участвует каждое четвёртое число.
Определение чисел Каталана Cn смотри в
справочнике.
Решение
а) Назовем весом последовательности такое число k, что частичные суммы s1 = a1, ..., sk = a1 + ... + ak положительны, а sk+1 ≤ 0 (если k < n). Рассмотрим циклический сдвиг, после которого образуется последовательность {b1, ..., bn} наибольшего веса. Докажем, что этот вес равен n. Пусть это не так, тогда рассмотрим наиболее "длинную" неположительную частичную сумму b1 + ... + bk. Тогда все суммы bk+1, bk+1 + bk+2, ..., bk+1 + ... + bn положительны. Это значит, что переставив bk+1, ..., bn в начало последовательности, мы увеличим ее вес. Противоречие.
Пусть есть два разных циклических сдвига, удовлетворяющих условию. Например, и у {a1, a2, ..., an} и у {am, ..., an, a1, ..., am–1} все частичные суммы положительны. Тогда числа a1 + ... + am–1 и am + ... + an натуральные, а их сумма равна 1. Противоречие.
б) Количество последовательностей из n + 1 единиц и n минус единиц равно Из а) следует, что количество таких последовательностей, у которых все частичные суммы положительны, равно
Отбросив у каждой первый член (который равен 1), мы получим все последовательности из задачи 60447, а их Cn.
Последнее равенство следует из того, что (2n)! = 1·3·...·(2n – 1)·2·4·...·2n = 2·6·...·(4n – 2)·1·2·...·n = (4n – 2)!!!!·n!.
Замечания
См. также задачу 98842.
Источники и прецеденты использования
| книга | |
| Автор | Алфутова Н.Б., Устинов А.В. |
| Год издания | 2002 |
| Название | Алгебра и теория чисел |
| Издательство | МЦНМО |
| Издание | 1 |
| глава | |
| Номер | 2 |
| Название | Комбинаторика |
| Тема | Комбинаторика |
| параграф | |
| Номер | 5 |
| Название | Числа Каталана |
| Тема | Классическая комбинаторика |
| задача | |
| Номер | 02.117 |
