МАЛЫЙ МЕХМАТ МГУ

Кружок 9-11 классов

Комбинаторика 1

1.

а)

В Стране Чудес есть три города \(A\), \(B\) и \(C\). Из города \(A\) в город \(B\) ведет 5 дорог, а из города \(B\) в город \(C\) — 7 дорог. Сколькими способами можно проехать от \(A\) до \(C\) через \(B\)?

б)

В этой стране построили еще один город \(D\) и несколько новых дорог — две из \(A\) в \(D\) и две из \(D\) в \(C\). Сколькими способами можно теперь добраться из города \(A\) в город \(C\)?

2.

В магазине "Все для чая" 5 видов чашек и 7 видов блюдец. Сколько различных пар "чашка \(+\) блюдце" можно собрать?

3.

а)

Сколькими способами можно поставить 5 книг в пятиместную полку?

б)

А \(n\) книг в \(n\)-местную?

4.

Сколько различных слов (не обязательно осмысленных) можно получить из слова КРОТ?

5.

а)

Сколькими способами можно разложить 25 одинаковых носков по 5 ящикам комода?

б)

Тот же вопрос для \(n\) носков и \(k\) ящиков.

6.

а)

Сколько существует различных семизначных телефонных номеров (считается, что номер начинаться с нуля не может)?

б)

А сколько семизначных номеров, в которых все цифры разные?

7.

а)

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

б)

А если в классе \(n\) человек, то сколькими способами можно выбрать \(k\) дежурных?

8.

На плоскости отмечено 10 точек так, что никакие три из них не лежат на одной прямой. Сколько существует треугольников с вершинами в этих точках?

Дополнительный листок

9.

Сколько различных слов (не обязательно осмысленных) можно получить из слова: а) КРОТ; б) КУСОК; в) КОЛОБОК; г) \(\underbrace{AA\ldots A}_{\mbox{a}}\underbrace{BB\ldots B}_{\mbox{b}}\)?

10.

Номер автомашины состоит из трех букв русского алфавита (используется 30 букв) и трех цифр: сначала идет буква, затем три цифры, а затем еще две буквы. Сколько существует различных номеров автомашин?

11.

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

12.

Сколькими способами можно составить букет из 17 цветков, если в продаже имеются гвоздики, розы, гладиолусы, ирисы, тюльпаны и васильки?

13.

Известно, что в выпуклом \(n\)-угольнике (\(n>3\)) никакие 3 диагонали не проходят через одну точку. Найдите число точек (отличных от вершины) пересечения пар диагоналей.

14.

а)

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

б)

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

15.

Сколько существует 9-значных чисел, цифры которых расположены в порядке убывания (то есть каждая следующая меньше предыдущей)?