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

Имеется 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 из них не имеют одинаковых цифр ни в одном разряде.