Олимпиадные задачи из источника «глава 2. Комбинаторика» для 11 класса - сложность 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>. Требуется провести ладью из левого нижнего угла в правый верхний. Двигаться можно только вверх и вправо, не заходя при этом на клетки главной диагонали и ниже нее. (Ладья оказывается на главной диагонали только в начальный и в конечный моменты времени.) Сколько у ладьи существует таких маршрутов?
В классе 30 учеников. Сколькими способами они могут пересесть так, чтобы ни один не сел на своё место?
Какое слагаемое в разложении (1 + <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60420/problem_60420_img_2.gif">)<sup>100</sup> по формуле бинома Ньютона будет наибольшим?
Найдите <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><sub>1</sub> + ... + <i>x<sub>m</sub></i>)<sup><i>n</i></sup> = <img align="MIDDLE" border="0" src="/storage/problem-media/60400/problem_60400_img_2.gif"> коэффициенты <i>C</i>(<i>k</i><sub>1</sub>,..., <i>k<sub>m</sub></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">)<sup>100</sup>; б) (<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>...
Докажите справедливость формулы <img align="absmiddle" src="/storage/problem-media/60388/problem_60388_img_2.gif">