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

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

Имеется куб размером 10×10×10, состоящий из маленьких единичных кубиков. В центре <i>O</i> одного из угловых кубиков сидит кузнечик. Он может прыгать в центр кубика,имеющего общую грань с тем, в котором кузнечик находится в данный момент; причём так, чтобы расстояние до точки <i>O</i> увеличивалось. Сколькими способами кузнечик может допрыгать до кубика, противоположного исходному?

Найдите число прямоугольников, составленных из клеток доски с <i>m</i> горизонталями и <i>n</i> вертикалями, которые содержат клетку с координатами  (<i>p, q</i>).

На каждом борту лодки должно сидеть по четыре человека. Сколькими способами можно выбрать команду для этой лодки, если есть 31 кандидат, причём десять человек хотят сидеть на левом борту лодки, двенадцать – на правом, а девяти безразлично где сидеть?

Ладья стоит на левом поле клетчатой полоски 1×30 и за ход может сдвинуться на любое количество клеток вправо.

  а) Сколькими способами она может добраться до крайнего правого поля?

  б) Сколькими способами она может добраться до крайнего правого поля ровно за семь ходов?

Сколькими способами можно разделить колоду из 36 карт пополам так, чтобы в каждой половине было по два туза?

Сколько существует целых чисел от 0 до 999999, в десятичной записи которых нет двух стоящих рядом одинаковых цифр?

а) Найдите сумму всех трёхзначных чисел, которые можно записать с помощью цифр 1, 2, 3, 4 (цифры могут повторяться).

б) Найдите сумму всех семизначных чисел, которые можно получить всевозможными перестановками цифр 1, ..., 7.

Труппа театра состоит из 20 артистов. Сколькими способами можно выбрать из неё в течение двух вечеров по шестьчеловек для участия в спектаклях так, чтобы ни один артист не участвовал в двух спектаклях?

Сколько различных четырёхзначных чисел, делящихся на 4, можно составить из цифр 1, 2, 3 и 4,

  а) если каждая цифра может встречаться только один раз?

  б) если каждая цифра может встречаться несколько раз?

Сколькими способами можно построить замкнутую ломаную, вершинами которой являются вершины правильного шестиугольника (ломаная может быть самопересекающейся)?

а) Спортивный клуб насчитывает 30 членов, из которых надо выделить четыре человека для участия в забеге на 1000 метров. Сколькими способами это можно сделать?

б) Сколькими способами можно составить команду из четырёх человек для участия в эстафете  100 м + 200 м + 300 м + 400 м?

Сколько ожерелий можно составить из пяти одинаковых красных бусинок и двух одинаковых синих бусинок?

На полке стоит 12 книг. Сколькими способами можно выбрать из них пять книг, никакие две из которых не стоят рядом?

Сколькими способами можно представить 1000000 в виде произведения трёх множителей, если произведения, отличающиеся порядком множителей,

  а) считаются различными?

  б) считаются тождественными?

Сколькими способами можно выложить в ряд пять красных, пять синих и пять зелёных шаров так, чтобы никакие два синих шара не лежали рядом?

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

  б) Решите ту же задачу, если голосование – тайное, то есть учитывается лишь число голосов, поданных за каждого кандидата, и не учитывается, кто за кого голосовал персонально.

Сколькими способами четыре чёрных шара, четыре белых шара и четыре синих шара можно разложить в шесть различных ящиков?

Сколькими способами три человека могут разделить между собой шесть одинаковых яблок, один апельсин, одну сливу и один мандарин?

Сколькими способами можно расположить в девяти лузах семь белых и два чёрных шара? Часть луз может быть пустой, а лузы считаются различными.

Поезду, в котором находится <i>m</i> пассажиров, предстоит сделать <i>n</i> остановок.

  а) Сколькими способами могут выйти пассажиры на этих остановках?

  б) Решите ту же задачу, если учитывается лишь количество пассажиров, вышедших на каждой остановке.

В почтовом отделении продаются открытки 10 видов. Сколькими способами можно купить в нём

  а) 12 открыток;

  б) 8 открыток;

  в) 8 различных открыток?

30 человек голосуют по пяти предложениям. Сколькими способами могут распределиться голоса, если каждый голосует только за одно предложение и учитывается лишь количество голосов, поданных за каждое предложение?

Сколькими способами можно разрезать ожерелье, состоящее из 30 различных бусин на 8 частей (резать можно только между бусинами)?

Переплетчик должен переплести 12 одинаковых книг в красный, зелёный или синий переплеты. Сколькими способами он может это сделать?