Олимпиадные задачи из источника «глава 2. Комбинаторика» для 8 класса - сложность 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 гостей в четырёх комнатах, если требуется, чтобы ни одна из комнат не осталась пустой?
Сколько существует целых чисел от 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?
В разложении (<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">
Вычислите суммы: 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">
При игре в преферанс каждому из трёх игроков раздают по 10 карт, а две карты кладут в прикуп. Сколько различных раскладов возможно в этой игре? (Считаются возможные раздачи без учета того, что каждые 10 карт достаются конкретному игроку.)
Имеется множество <i>C</i>, состоящее из <i>n</i> элементов. Сколькими способами можно выбрать в <i>C</i> два подмножества <i>A</i> и <i>B</i> так, чтобы
а) множества <i>A</i> и <i>B</i> не пересекались;
б) множество <i>A</i> содержалось бы в множестве <i>B</i>?
Сколькими способами можно разделить на команды по 6 человек для игры в волейбол группу:
а) из 12; б) из 24 спортсменов?
Параллелограмм пересекается двумя рядами прямых, параллельных его сторонам; каждый ряд состоит из <i>m</i> прямых.
Сколько параллелограммов можно выделить в образовавшейся сетке?
В выпуклом <i>n</i>-угольнике проведены все диагонали. Они разбивают его на выпуклые многоугольники. Возьмём среди них многоугольник с самым большим числом сторон.
Сколько сторон он может иметь?
Докажите, что для любого натурального <i>a</i> найдётся такое натуральное <i>n</i>, что все числа <i>n</i> + 1, <i>n<sup>n</sup></i> + 1, <i>n<sup>n<sup>n</sup></sup></i> + 1, ... делятся на <i>a</i>.
Докажите справедливость формулы <img align="absmiddle" src="/storage/problem-media/60388/problem_60388_img_2.gif">