Олимпиадные задачи из источника «глава 2. Комбинаторика»

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

<b><em>Слоны, носороги, жирафы.</em></b>Во всех зоопарках, где есть слоны и носороги, нет жирафов. Во всех зоопарках, где есть носороги и нет жирафов, есть слоны. Наконец, во всех зоопарках, где есть слоны и жирафы, есть и носороги. Может ли быть такой зоопарк, в котором есть слоны, но нет ни жирафов, ни носорогов?

Имеется 1955 точек. Какое максимальное число троек можно из них выбрать так, чтобы каждые две тройки имели ровно одну общую точку?

Числа 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. Из каждого ящика вынимается по одному шару. Какова вероятность того, что а) вынуты три единицы; б) вынуты три равных числа?