Олимпиадные задачи из источника «глава 2. Комбинаторика» - сложность 2 с решениями
Докажите, что числа Каталана удовлетворяют рекуррентному соотношению <i>C<sub>n</sub></i> = <i>C</i><sub>0</sub><i>C</i><sub><i>n</i>–1</sub> + <i>C</i><sub>1</sub><i>C</i><sub><i>n</i>–2</sub> + ... + <i>C</i><sub><i>n</i>–1</sub><i>C</i><sub>0</sub>.
Определение чисел Каталана <i>C<sub>n</sub></i> смотри в <a href="https://problems.ru/thes.php?letter=23#chisla_catalana">справочнике</a>.
Билеты стоят 50 центов, и 2<i>n</i> покупателей стоят в очереди в кассу. Половина из них имеет по одному доллару, остальные – по 50 центов. Кассир начинает продажу билетов, не имея денег. Сколько существует различных порядков в очереди, таких, что кассир всегда может дать сдачу?
Рассмотрим шахматную доску <i>n×n</i>. Требуется провести ладью из левого нижнего угла в правый верхний. Двигаться можно только вверх и вправо, не заходя при этом на клетки главной диагонали и ниже нее. (Ладья оказывается на главной диагонали только в начальный и в конечный моменты времени.) Сколько у ладьи существует таких маршрутов?
Сколькими способами можно расселить 15 гостей в четырёх комнатах, если требуется, чтобы ни одна из комнат не осталась пустой?
В классе 30 учеников. Сколькими способами они могут пересесть так, чтобы ни один не сел на своё место?
Сколько существует целых чисел от 1 до 1000000, которые не являются ни полным квадратом, ни полным кубом, ни четвёртой степенью?
Сколько существует целых чисел от 1 до 33000, которые не делятся ни на 3, ни на 5, но делятся на 11?
Сколько существует целых чисел от 1 до 16500, которые
а) не делятся на 5;
б) не делятся ни на 5, ни на 3;
в) не делятся ни на 5, ни на 3, ни на 11?
Каждая сторона в треугольнике<i>ABC</i>разделена на 8 равных отрезков. Сколько существует различных треугольников с вершинами в точках деления (точки<i>A</i>,<i>B</i>,<i>C</i>не могут быть вершинами треугольников), у которых ни одна сторона не параллельна ни одной из сторон треугольника<i>ABC</i>?
Из 100 студентов университета английский язык знают 28 студентов, немецкий — 30, французский — 42, английский и немецкий — 8, английский и французский — 10, немецкий и французский — 5, все три языка знают 3 студента. Сколько студентов не знают ни одного из трех языков?
Докажите справедливость равенства<div align="CENTER"> <table> <tr valign="MIDDLE"><td align="LEFT">| <i>A</i><sub>1</sub> $\displaystyle \cup$ <i>A</i><sub>2</sub> $\displaystyle \cup$...$\displaystyle \cup$ <i>A</i><sub>n</sub>| = | <i>A</i><sub>1</sub>| +...+ | <i>A</i><sub>n</sub>| - | <i>A</i><sub>1</sub> $\displaystyle \cap$ <i>A</i><sub>2</sub>| -</td> </tr> <tr valign="MIDDLE"><td align="LEFT"> - | <i>A</i><sub>1</sub> $\displaystyle \cap$ <i>A</i><sub>3</sub>| -...-...
Пусть имеется<i>n</i>подмножеств<i>A</i><sub>1</sub>, ...,<i>A</i><sub>n</sub>конечного множества<i>E</i>и$\chi_{j}^{}$(<i>x</i>) — характеристические функции этих множеств, то есть<div align="CENTER"> $\displaystyle \chi_{j}^{}$(<i>x</i>) = <img width="112" height="54" align="MIDDLE" border="0" src="/storage/problem-media/60434/problem_60434_img_4.gif" alt="\begin{displaymath}\begin{cases} 1,& x\in A_j,\ 0,& x\in E\setminus A_j \end{cases}\end{displaymath}">(<i>j</i> = 1,..., <i>n</i>). </div> Докажите, что при этом$\chi$(<i>x</i>) — характеристическая функция мн...
В классе имеется <i>a</i><sub>1</sub> учеников, получивших в течение года хотя бы одну двойку, <i>a</i><sub>2</sub> учеников, получивших не менее двух двоек, ..., <i>a<sub>k</sub></i> учеников, получивших не менее <i>k</i> двоек. Сколько всего двоек в этом классе? (Предполагается, что ни у кого нет более <i>k</i> двоек.)
У игрока в преферанс оказалось 4 козыря, а еще 4 находятся на руках у двух его противников. Какова вероятность того, что козыри лягут а) 2 : 2; б) 3 : 1; в) 4 : 0?
Пишется наудачу некоторое двузначное число. Какова вероятность того, что сумма цифр этого числа равна 5?
<div align="center"><img src="/storage/problem-media/60424/problem_60424_img_2.gif"></div>Здесь изображен фрагмент таблицы, которая называется<i>треугольником Лейбница</i>. Его свойства "аналогичны в смысле противоположности" свойствам треугольника Паскаля. Числа на границе треугольника обратны последовательным натуральным числам. Каждое число внутри равно сумме двух чисел, стоящих под ним. Найдите формулу, которая связывает числа из треугольников Паскаля и Лейбница.
Какое слагаемое в разложении (1 + <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60420/problem_60420_img_2.gif">)<sup>100</sup> по формуле бинома Ньютона будет наибольшим?
Найдите <i>m</i> и <i>n</i> зная, что <img align="absmiddle" src="/storage/problem-media/60419/problem_60419_img_2.gif">
В компании из 10 человек произошло 14 попарных ссор. Докажите, что все равно можно составить компанию из трёх друзей.
Покажите, что любое натуральное число <i>n</i> может быть представлено в виде <img align="absmiddle" src="/storage/problem-media/60417/problem_60417_img_2.gif"> где <i>x, y, z</i> – такие целые числа, что 0 ≤ <i>x < y < z</i>, либо 0 = <i>x = y < z</i>.
В разложении (<i>x + y</i>)<sup><i>n</i></sup> по формуле бинома Ньютона второй член оказался равен 240, третий – 720, а четвёртый – 1080. Найдите <i>x, y</i> и <i>n</i>.
120 одинаковых шаров плотно уложены в виде правильной треугольной пирамиды. Сколько шаров лежит в основании?
Докажите равенство <img align="absmiddle" src="/storage/problem-media/60414/problem_60414_img_2.gif">
Докажите тождества: а) <img align="absmiddle" src="/storage/problem-media/60413/problem_60413_img_2.gif"> б) <img align="absmiddle" src="/storage/problem-media/60413/problem_60413_img_3.gif"> в) <img align="absmiddle" src="/storage/problem-media/60413/problem_60413_img_4.gif"> г) <img align="absmiddle" src="/storage/problem-media/60413/problem_60413_img_5.gif"> д) <img align="absmiddle" src="/storage/problem-media/60413/problem_60413_img_6.gif">(Попробуйте доказать эти тождества тремя разными способами: пользуясь тем, что <img align="absmiddle" src="/storage/problem-media/60413/problem_60413_img_7.gif"> – это количест...
Вычислите суммы: a) <img align="absmiddle" src="/storage/problem-media/60412/problem_60412_img_2.gif"> б) <img align="absmiddle" src="/storage/problem-media/60412/problem_60412_img_3.gif"> в) <img align="absmiddle" src="/storage/problem-media/60412/problem_60412_img_4.gif">