Олимпиадные задачи из источника «глава 2. Комбинаторика» для 6-11 класса - сложность 1-2 с решениями
<b><em>Слоны, носороги, жирафы.</em></b>Во всех зоопарках, где есть слоны и носороги, нет жирафов. Во всех зоопарках, где есть носороги и нет жирафов, есть слоны. Наконец, во всех зоопарках, где есть слоны и жирафы, есть и носороги. Может ли быть такой зоопарк, в котором есть слоны, но нет ни жирафов, ни носорогов?
Докажите, что числа Каталана удовлетворяют рекуррентному соотношению <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?
Имеется три ящика, в каждом из которых лежат шары с номерами от 0 до 9. Из каждого ящика вынимается по одному шару. Какова вероятность того, что а) вынуты три единицы; б) вынуты три равных числа?
Пишется наудачу некоторое двузначное число. Какова вероятность того, что сумма цифр этого числа равна 5?
В ящике имеется 10 белых и 15 чёрных шаров. Из ящика вынимаются четыре шара. Какова вероятность того, что все вынутые шары будут белыми?
<div align="center"><img src="/storage/problem-media/60424/problem_60424_img_2.gif"></div>Здесь изображен фрагмент таблицы, которая называется<i>треугольником Лейбница</i>. Его свойства "аналогичны в смысле противоположности" свойствам треугольника Паскаля. Числа на границе треугольника обратны последовательным натуральным числам. Каждое число внутри равно сумме двух чисел, стоящих под ним. Найдите формулу, которая связывает числа из треугольников Паскаля и Лейбница.
Сколько существует различных возможностей рассадить 5 юношей и 5 девушек за круглый стол с 10 креслами так, чтобы они чередовались?
Сколько четырёхзначных чисел можно составить, используя цифры 1, 2, 3, 4 и 5, если:
а) никакая цифра не повторяется более одного раза;
б) повторения цифр допустимы;
в) числа должны быть нечётными и повторений цифр быть не должно?
Какое слагаемое в разложении (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>.