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

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

Руководители Алексей Сергеевич Воропаев и Юрий Александрович Цимбалов
2010/2011 учебный год

Занятие 17 (12 февраля 2011 года). Комбинаторика

В некоторых из следующих задач очень пригодится факториал: n·(n − 1)·...·2·1 = n! (произносится как «n факториал»). Часто бывает удобна такая запись: n·(n − 1)·...·(k + 1) = n!/k!.
1.
а)
Из города А в город Б есть 5 дорог, из Б в город В — 9 дорог, а из В в А — 5 дорог. Сколькими способами можно проехать по маршруту А-Б-В-А?
б)
В магазине есть 5 чашек, 9 тарелок и 5 ложек. Сколько есть способов выбрать там набор из чашки, тарелки и ложки?
в)
Злоумышленник пытается взломать кодовый замок сейфа. Из надёжных источников ему стало известно, что это чётное трёхзначное число, вторая цифра которого нечётна. Сколько попыток ему потребуется, чтобы взломать сейф?
2.
Сколькими способами можно расставить n человек в ряд?
В математике эти способы обычно называют перестановками. Конечно, переставлять можно не только людей в ряду.
3.
а)
Сколькими способами можно выбрать троих из пяти лыжников и распределить между ними золото, серебро и бронзу?
б)
Тот же вопрос для n спортсменов и k призовых мест.
Такие способы называют размещениями. Количество размещений обычно обозначается, как Ank.
4.
а)
Из 10 претендентов нужно выбрать троих школьников для участия в математической олимпиаде. Сколькими способами это можно сделать?
б)
Тот же вопрос для n претендентов и k участников.
Такие способы называют сочетаниями. Число сочетаний обычно обозначается, как Cnk. Да и вместо «число сочетаний» произносят обычно просто «це из эн по ка».

* * *

5.
В первом классе читать умеют 12 учеников, считать — 8, писать — 9; читать и писать — 4, читать и считать — 5, писать и считать — 3; читать, писать и считать — 2; 6 учеников до сих пор ничему не научились. Сколько учеников в классе?
6.
Сколько существует способов разложить 25 одинаковых носков по 5 ящикам комода?
7.
Сколько диагоналей имеет выпуклый: а) 10-угольник; б) k-угольник?
8.
Сколько разных бус можно составить из семи разноцветных бусин?
9.
Сколькими способами можно поставить на шахматную доску а) 8 ладей? б) 4 чёрных и 4 белых фигуры: коня, слона, ладью и ферзя?
10.
На прямой отмечено 10 точек, а на параллельной ей прямой — 11 точек. Сколько существует а) треугольников; б) четырехугольников с вершинами в этих точках?