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

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

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

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

Докажите, что числа Каталана удовлетворяют рекуррентному соотношению   <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;;

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

В классе 30 учеников. Сколькими способами они могут пересесть так, чтобы ни один не сел на своё место?

Найдите суммы рядов   а)  <img align="absmiddle" src="/storage/problem-media/60427/problem_60427_img_2.gif">

  б)  <img align="absmiddle" src="/storage/problem-media/60427/problem_60427_img_3.gif">

  в)  <img align="absmiddle" src="/storage/problem-media/60427/problem_60427_img_4.gif">  (<i>r</i> ≥ 2).

Найдите сумму (см. задачу <a href="https://mirolimp.ru/tasks/160424">160424</a> про треугольник Лейбница):

  ¹/₁₂ + ¹/₃₀ + ¹/₆₀ + ¹/₁₀₅ + ...

и обобщите полученный результат.

Докажите равенства (см. <i>треугольник Лейбница</i>, задача <a href="https://mirolimp.ru/tasks/160424">160424</a>):   а) 1 = ¹/₂ + ¹/₆ + ¹/₁₂ + ¹/₂₀ + ¹/₃₀ + ... ;   б) ¹/₂ = ¹/₃ + ¹/₁₂ + ¹/₃₀ + ¹/₆₀ + ¹/₁₀₅ + ... ;   в) ¹/<sub>3&...

Какое слагаемое в разложении  (1 + <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60420/problem_60420_img_2.gif">)¹⁰⁰  по формуле бинома Ньютона будет наибольшим?

Найдите <i>m</i> и <i>n</i> зная, что   <img align="absmiddle" src="/storage/problem-media/60419/problem_60419_img_2.gif">

В компании из 10 человек произошло 14 попарных ссор. Докажите, что все равно можно составить компанию из трёх друзей.

Докажите тождества:   а)  <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">

Придумайте какой-нибудь способ достроить треугольник Паскаля вверх.

Докажите, что в равенстве   (<i>x</i>₁ + ... + <i>x_m</i>)^<i>n</i>  = <img align="MIDDLE" border="0" src="/storage/problem-media/60400/problem_60400_img_2.gif">   коэффициенты  <i>C</i>(<i>k</i>₁,..., <i>k_m</i>)  могут быть найдены по формуле   <img align="MIDDLE" border="0" src="/storage/problem-media/60400/problem_60400_img_3.gif">

Сколько рациональных слагаемых содержится в разложении а) (<img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60389/problem_60389_img_2.gif"> + <img width="26" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60389/problem_60389_img_3.gif">)¹⁰⁰; б) (<img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60389/problem_60389_img_2.gif"> + <img width="26" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60389/problem_60389_img_4.gif">)<sup>300</sup&gt...

Докажите справедливость формулы   <img align="absmiddle" src="/storage/problem-media/60388/problem_60388_img_2.gif">

Дано 51 различное двузначное число (однозначные числа считаем двузначными с первой цифрой 0). Докажите, что из них можно выбрать 6 таких чисел, что никакие 2 из них не имеют одинаковых цифр ни в одном разряде.