Олимпиадные задачи из источника «глава 2. Комбинаторика» для 9-10 класса - сложность 1-4 с решениями

На двух клетках шахматной доски стоят чёрная и белая фишки. За один ход можно передвинуть любую из них на соседнюю по вертикали или горизонтали клетку (две фишки не могут стоять на одной клетке). Могут ли в результате таких ходов встретиться все возможные варианты расположения этих двух фишек, причём ровно по одному разу?

Числа 1, 2, 3, ..., 101 выписаны в ряд в каком-то порядке.

Докажите, что из них можно вычеркнуть 90 так, что оставшиеся 11 будут расположены по их величине (либо возрастая, либо убывая).

На сколько частей разделяют<i>n</i>-угольник его диагонали, если никакие три диагонали не пересекаются в одной точке?

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

Определение чисел Каталана <i>C_n</i> смотри в <a href="https://problems.ru/thes.php?letter=23#chisla_catalana">справочнике</a>.

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

{<i>a</i>₁, <i>a</i>₂, ..., <i>a_n</i>},  {<i>a</i>₂, ..., <i>a_n</i>, <i>a</i>₁},  ...,  {<i>a_n</i>, <i>a</i>₁, ..., <i>a</i>_<i>n</i>–1}  все частичные суммы (от начала до произвольного элемента) положит...

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

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

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

Сколько последовательностей  {<i>a</i>₁, <i>a</i>₂, ..., <i>a</i>_2<i>n</i>},  состоящих из единиц и минус единиц, обладают тем свойством, что  <i>a</i>₁ + <i>a</i>₂ + ... + <i>a</i>_2<i>n</i> = 0,  а все частичные суммы  <i>a</i>₁,  <i>a</i>₁ + <i>a</i>₂,  ...,  <i>a</i>₁ + <i>a</i>₂ + ... + <i>a</i>_2<i>n</i>  неотрицательны?

Докажите, что в условии задач <a href="https://mirolimp.ru/tasks/160445">160445</a> б) и в) числа ¹/₅ и ¹/₂₀ нельзя заменить большими величинами. >

В прямоугольнике площади 1 расположено пять фигур площади ½ каждая. Докажите, что найдутся

  а) две фигуры, площадь общей части которых не меньше ³/₂₀;

  б) две фигуры, площадь общей части которых не меньше &frac15;;

  в) три фигуры, площадь общей части которых не меньше ¹/₂₀.

Сколькими способами можно расселить 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>₁ $\displaystyle \cup$ <i>A</i>₂ $\displaystyle \cup$...$\displaystyle \cup$ <i>A</i>_n| = | <i>A</i>₁| +...+ | <i>A</i>_n| - | <i>A</i>₁ $\displaystyle \cap$ <i>A</i>₂| -</td> </tr> <tr valign="MIDDLE"><td align="LEFT">         - | <i>A</i>₁ $\displaystyle \cap$ <i>A</i>₃| -...-...

Пусть имеется<i>n</i>подмножеств<i>A</i>₁, ...,<i>A</i>_nконечного множества<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>₁ учеников, получивших в течение года хотя бы одну двойку, <i>a</i>₂ учеников, получивших не менее двух двоек, ..., <i>a_k</i> учеников, получивших не менее <i>k</i> двоек. Сколько всего двоек в этом классе? (Предполагается, что ни у кого нет более <i>k</i> двоек.)

У игрока в преферанс оказалось 4 козыря, а еще 4 находятся на руках у двух его противников. Какова вероятность того, что козыри лягут а) 2 : 2; б) 3 : 1; в) 4 : 0?

Имеется три ящика, в каждом из которых лежат шары с номерами от 0 до 9. Из каждого ящика вынимается по одному шару. Какова вероятность того, что а) вынуты три единицы; б) вынуты три равных числа?

Пишется наудачу некоторое двузначное число. Какова вероятность того, что сумма цифр этого числа равна 5?

В ящике имеется 10 белых и 15 чёрных шаров. Из ящика вынимаются четыре шара. Какова вероятность того, что все вынутые шары будут белыми?