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

Кружок 8 класса

Занятия 3 и 4. Комбинаторика

Теоретические сведения

I. Перестановки n элементов

Допустим, мы выбираем все n элементов из множества, содержащего n элементов, упорядоченным образом. Такие размещения n элементов называются перестановками n элементов. Число перестановок n элементов обозначается через P_n.

Утверждение. P_n = n!, где n! = 1·2·…·n — произведение всех натуральных чисел от 1 до n (читается «эн факториал»).
Доказательство. Будем строить произвольную перестановку n элементов. На первое место мы можем поставить любой из n элементов. После того, как первый элемент выбран, остается (n-1) способ выбрать второй элемент из оставшихся. Для каждого способа выбрать первый и второй элементы есть (n-2) способа выбрать третий элемент, и так далее. Если уже выбран (n-1) элемент перестановки, остается единственный способ выбрать последний элемент. Таким образом, чтобы посчитать количество возможных перестановок n элементов, нужно все эти числа перемножить: P_n = n·(n-1)·(n-2)·…·2· 1 = n!. Утверждение доказано.

II. Размещения из n элементов по k

1. Пусть у нас есть множество из n элементов, из которых мы хотим выбрать упорядоченные k различных элементов (то есть выбрать первый элемент, второй элемент и так далее вплоть до k-го). Каждый способ это сделать называется размещением без повторений. Способы считаются различными, если хотя бы на одном месте в них стоят различные элементы. Число таких способов называется числом размещений без повторений и обозначается A_n^k(читается: «а из эн по ка»).

2. Число способов выбрать упорядоченные k элементов из n, если им разрешено повторяться, называется числом размещений с повторениями и обозначается как A_n^k. Формула для его нахождения приводится в ответе к задаче 3.7.

III. Сочетания из n элементов по k

1. Мы выбираем из n элементов неупорядоченные k различных элементов. Каждый способ это сделать называется сочетанием из n элементов по k. Различные сочетания отличаются друг от друга составом, но не порядком элементов. Число сочетаний из n элементов по k (нетрудно заметить, что это в точности число подмножеств из k элементов в множестве из n элементов) обозначается C_n^k. Формула для его нахождения приведена в задаче 4.2.

2. Допустим, что у нас есть n различных типов элементов. Тогда комбинация из k элементов, при условии, что элементы одного типа могут встречаться несколько раз и порядок элементов в комбинации не важен, называется сочетанием с повторениями из n элементов по k. Число сочетаний с повторениями обозначается C_n^k. Формула для его нахождения приведена в задаче 4.6.

Задачи занятия №3

Размещения

3.1.

На вершину горы ведут пять тропинок.

a)

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

b)

А если турист не хочет спускаться по той же дороге, по которой он поднимался?

Ответ Решение

Ответ. а) 25; b) 20.

Решение.

а) У туриста есть пять способов подняться на гору. Для каждого из этих способов существует по пять возможностей спуститься вниз. Соответственно, способов подняться на гору, а затем спуститься с нее, существует ровно 5·5 = 25.

б) В отличие от пункта а, теперь для каждого из пяти способов подняться на гору есть лишь по четыре возможности спуститься: по той же дороге, по которой турист поднимался, спускаться уже нельзя. Так что в этом случае есть 5·4 = 20 возможных маршрутов.

3.2.

Пираты подняли бунт и захватили корабль. Теперь им нужно выбрать из своих рядов капитана, его первого помощника и боцмана. Сколькими способами они могут это сделать, если пиратов:

а)

4

b)

6

c)

20 и им ещё нужно выбрать кока?

Ответ Решение

Ответ. a) 24; b) 120; c) 116280.

Решение.

a) Выбрать капитана можно четырьмя способами. При каждом из четырех способов выбора капитана есть по три способа выбрать первого помощника из оставшихся пиратов. А при каждом способе выбора капитана и помощника выбрать боцмана можно двумя способами. Поэтому всего возможностей распределить должности будет 4·3·2=24.

b) Решение аналогично решению пункта а. 6·5·4=120.

с) Решение аналогично решению двух предыдущих пунктов. Вычислять произведение чисел 20·19·18·17 проще всего так: 20·19·18·17 = (20·18)·(18-1)·(18+1) = 360·(18²-1) = 360·(324-1) = 360·323 = 116280 (здесь мы пользовались формулой для разности квадратов). Последнее умножение в этой цепочке можно проделать в столбик, а можно продолжить преобразования и привести выражение к такому виду, чтобы все действия можно было выполнить в уме (попробуйте проделать это самостоятельно). Вычислить 18² можно при помощи формулы для квадрата суммы: 18² = (20-2)² = 20²-2·20·2+2² = 400-80+4 = 324.

3.3.

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

Ответ Решение

Ответ. 6¹⁵ = 470184984576.

Решение.

Пронумеруем лузы числами от 1 до 6. Составим таблицу: в ячейках верхней строки будем по порядку писать номера шаров от 1 до 15, а в k-й ячейке нижней строки — номер лузы, в которую попал k-й шар. Количество способов распределения шаров по лузам совпадает с количеством способов заполнить нижнюю строку такой таблицы.

Посчитаем это количество. Отметим, что в каждой ячейке нижней строки нашей таблицы может стоять любой номер от 1 до 6 (каждый из шаров может попасть в любую лузу). Поэтому число способов ее заполнить равно 6·6·…·6 = 6¹⁵ (произведение состоит из 15 сомножителей).

Точное значение числа 6¹⁵ находить не обязательно, но можно вычислить, что оно равно 470184984576. Попробуйте это сделать, используя умножение не более шести раз. Все действия выполняйте в уме или в столбик: калькулятором пользоваться запрещается!

3.4.

В комнате студенческого общежития живут трое студентов. У них есть 4 чашки, 5 блюдец и 6 чайных ложек (все чашки, блюдца и ложки отличаются друг от друга). Сколькими способами они могут накрыть стол для чаепития (то есть дать каждому студенту чашку, блюдце и ложку)?

Ответ Решение

Ответ. (4·3·2)·(5·4·3)·(6·5·4) = 172800.

Решение. Сначала отдельно посчитаем количество способов раздать студентам чашки, количество способов раздать им блюдца и количество способов раздать им чайные ложки. Например, количество способов раздать блюдца равно числу размещений без повторений четырех элементов из пяти A₅⁴ (см. «Теоретические сведения»). А оно равно 5·4·3 = 60 (подумайте почему; вспомните решение задачи 3.2). Аналогично вычисляются и два других числа способов: они будут равны, соответсвенно, 24 и 120. А теперь все полученные числа надо перемножить: 24·60·120 = 172800. Ведь раздача чашек, раздача блюдец и раздача ложек производятся независимо друг от друга. Постарайтесь произвести вычисления без калькулятора, выполняя умножение в столбик не более одного раза (а все остальное проделывая в уме).

3.5.

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

Ответ Решение

Ответ. 768 способами.

Решение.

Сначала выберем черное поле. Как известно, на шахматной доске 8·8=64 клетки, и ровно половина из них черные. Значит, выбрать черное поле можно 32 способами.

В каждой вертикали и в каждой горизонтали есть по четыре белые клетки. Значит, на одной вертикали или на одной горизонтали с любой выбранной черной клеткой лежат 8 белых клеток. Так как всего белых клеток на доске 32, то не лежащих на одной горизонтали или вертикали с нашей черной клеткой среди них будет 32-8 = 24. Тем самым есть 32 способа выбрать черную клетку, и для каждого из этих способов по 24 возможности выбрать белую клетку. Значит, всего возможностей выбрать пару разноцветных клеток, не лежащих на одной горизонтали или вертикали, будет 32·24 = 768.

3.6.

Четверо студентов сдавали экзамен.

a)

Сколькими способами им могли быть выставлены оценки, если известно, что все студенты экзамен сдали (то есть получили 3, 4 или 5)?

b)

А если студентов было 10?

Ответ Решение

Ответ. a) 3⁴ = 81; b) 3¹⁰ = 59049.

Решение. Решение этой задачи аналогично решению задачи 3.3. Число способов выставить студентам оценки равно числу способов поставить напротив каждой фамилии в ведомости оценку 3, 4 или 5. В пункте b) попробуйте проделать вычисления, пользуясь умножением лишь четыре раза и выполнив в столбик лишь одно из них.

3.7.

Выведите формулу для нахождения A_n^k.

Ответ Решение

Ответ. A_n^k = n^k.

Решение. Эта формула фактически доказана в частном случае при решении задачи 3.3. Если в условии той задачи взять k шаров и n луз и решать ее так же, как мы это делали в частном случае, как раз и получится результат, приведенный в ответе.

3.8.

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

а)

трех

b)

пяти

c)

семи букв, можно составить из тридцати трех букв русского алфавита так, чтобы любые две стоящие рядом буквы были различны?

Ответ Решение

Ответ. a) 33·32·32 = 33792; b) 33·32⁴ = 34603008; c) 33·32⁶ = 35433480192.

Решение. Первую букву слова можно выбрать 33 способами. Когда первая буква выбрана, вторая должна быть отлична от нее. Значит, вторую букву можно выбрать лишь 32 способами. По той же причине третью и каждую из последующих букв (если надо) можно выбрать 32 способами. Так что для слова из трех букв имеем 33·32·32 = 33792 возможности, для слова из пяти букв их будет 33·32⁴ = 34603008, а для слова из семи букв получим 33·32⁶ = 35433480192 (точные значения находить не обязательно).

3.9.

Сколько можно составить из тридцати трех букв русского алфавита шестибуквенных слов, содержащих хотя бы одну букву «а»?

Ответ Решение

Ответ. 33⁶ - 32⁶ = 217726145.

Решение. Сначала сосчитаем все возможные шестибуквенные слова (разумеется, неосмысленные тоже будет считать). Таких слов бывает 33⁶ (сравните с задачей №7). Теперь сосчитаем те слова, в которых вообще нет буквы «а». В них на каждом месте может стоять любая из 32 букв (все буквы, кроме буквы «а»). Значит, таких слов всего 32⁶. Остальные слова содержат хоть одну букву«а», и их количество равно 33⁶ - 32⁶ = 217726145. Вычисления можно сразу проводить в столбик, а можно сначала упростить выражение с помощью формул сокращенного умножения.

Перестановки

3.10.

Сколько пятизначных чисел содержат все цифры

а)

1, 2, 3, 4, 5?

b)

0, 2, 4, 6, 8?

Ответ Решение

Ответ. а) 120; b) 96.

Решение.

a) Ясно, что искомые числа состоят из цифр 1, 2, 3, 4, 5, расставленных в разном порядке. Значит, количество таких чисел равно количеству способов упорядочить множество из пяти цифр. На первое место можно поставить любую цифру от 1 до 5. После того как первая цифра выбрана, вторую можно выбрать четырьмя способами. Когда выбраны первая и вторая цифры, третью можно выбрать тремя способами, и так далее. Значит, всего искомых чисел 5·4·3·2·1 = 5! = 120 (сравните с пунктом I «Теоретических сведений»).

b) Здесь, в отличие от пункта а, на первое место можно поставить не любую цифру: число не может начинаться с нуля. Поэтому на первом месте может стоять любая из четырех, а не пяти, цифр. Дальнейшие рассуждения полностью аналогичны предыдущим. Так что всего искомых чисел будет 4·4·3·2·1 = 96.

3.11.

В азбуке Морзе используются два типа символов: точки (·) и тире (—). Можно ли сопоставить каждой букве русского алфавита такой код, чтобы каждая буква оказалась зашифрована не более чем четырьмя символами азбуки Морзе?

Ответ Решение

Ответ. Нельзя.

Решение. Посчитаем количество возможных комбинаций из четырех символов азбуки Морзе. На каждом месте в такой комбинации может стоять любой из двух символов. Значит, всего комбинаций из четырех символов будет 2·2·2·2 = 16. Но можно использовать и комбинации меньшего числа символов. Аналогично предыдущему находим, что из трех символов можно составить 2³ = 8 комбинаций, из двух — 2·2 = 4 комбинации, а из одного символа — две комбинации. Сложив эти числа, получим 16+8+4+2 = 30 < 33. Так что весь русский алфавит зашифровать таким способом не получится. А вот латинский — получится: в нем всего 26 букв.

3.12.

a)

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

b)

А n ладей на доске размера n×n?

Ответ Решение

Ответ. a) 8! = 51840; b) n!.

Решение. Чтобы ладьи не били друг друга, необходимо, чтобы на каждой вертикали и на каждой горизонтали стояла ровно одна ладья. Будем расставлять ладьи следующим образом: первую ладью ставим на первую горизонталь, вторую ладью — на вторую, и т. д., но так, чтобы они все были на разных вертикалях. То есть надо заполнить таблицу, в верхней строке которой стоят номера ладей (или, что то же самое, горизонталей) по порядку, а в нижней номера вертикалей. Число способов сделать это равно числу способов упорядочить 8 (или n) чисел. А оно равно 8! = 51840 (или, соответственно, n!).

3.13.

Каких семизначных чисел больше: тех, в записи которых есть единица, или всех остальных?

Ответ Решение

Ответ. Чисел с единицами больше.

Решение. Проще сначала посчитать количество семизначных чисел, в которых единиц нет. В таком числе на первом месте может стоять любая цифра, кроме 0 и 1, а на всех остальных — любые цифры, кроме 1. Значит, таких чисел всего 8·9⁶. А всего семизначных чисел бывает 9·10⁶ (на первом месте может стоять любая цифра, кроме нуля, а на всех остальных — любые цифры). Тем самым семизначных чисел, содеращих единицу, будет 9·10⁶ − 8·9⁶. Это число надо сравнить с числом 8·9⁶. Результат сравнения будет таким же, как результат сравнения чисел 9·10⁶ и 8·9⁶ + 8·9⁶ = 16·9⁶ (убедитесь в этом сами). А результат сравнения этих чисел, в свою очередь, совпадает с результатом сравнения чисел 10⁶ и 16·9⁵. Первое из этих чисел, очевидно, равно 1000000, а второе, как можно подсчитать в столбик, равно 944784. Значит, второе из первоначально сравниваемых чисел также меньше первого. Тем самым семизначных чисел, содержащих единицу, больше, чем всех остальных.

Задачи занятия №4

Сочетания без повторений

4.1.

Сколькими способами можно выбрать баскетбольную команду (5 человек) из

а)

шести человек?

b)

семи человек?

c)

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

Ответ Решение

Ответ. a) 6; b) 21; c) 252.

Решение.

a) Выбрать пять человек из шести — все равно, что выбрать одного, которого в команду не возьмут. А выбрать одного человека из шести, очевидно, можно шестью способами.

b) Аналогично предыдущему, выбрать пять человек из семи — все равно, что выбрать двух. Первого человека можно выбрать 7 способами, а второго после этого — шестью. То есть если важно, кто первый, а кто второй, число способов это сделать равно 7·6 = 42. Но одну и ту же пару человек можно упорядочить двумя способами. Значит, число неупорядоченных пар, выбранных из семи человек, равно 42:2 = 21.

c) Набрать две команды по пять человек из десяти претендентов — все равно что набрать одну команду, а из остальных претендентов составить другую. Посчитаем число способов выбрать пять человек из 10. Если порядок важен, то есть 10·9·8·7·6 способов это сделать. Но существует 5! = 120 способов упорядочить 5 человек (вспомните задачу 3.10 а). Так что каждому способу выбрать 5 человек неупорядоченным образом соответствует 120 способов выбрать их упорядоченным образом. Значит, количество способов набрать команду из пяти человек в 120 раз меньше, чем 10·9·8·7·6. А это, как нетрудно посчитать, есть в точности 252.

4.2.

Проверьте формулу

Cnk	=	Ank	=	n!	.
		k!		(n-k)! k!

Решение

Решение.

Второе равенство в этой формуле следует из формулы для A_n^k, приведенной в «Теоретических сведениях». Докажем первое равенство. Заметим, что для каждой неупорядоченной выборки из k элементов существует k! способов ее упорядочить (вспомните утверждение из п. I «Теоретических сведений»). То есть каждой неупорядоченной выборке из k элементов соответствуют k! различных упорядоченных выборок того же объема (то есть с тем же количеством элементов).

Упорядоченные выборки, полученные из разных неупорядоченных выборок, различны (хотя бы потому, что состоят из различных элементов). Каждую упорядоченную выборку можно получить из какой-то неупорядоченной (а именно той, которая состоит из элементов интересующей нас упорядоченной). Тем самым доказано, что упорядоченных выборок из k элементов ровно в k! раз больше, чем неупорядоченных выборок того же объема. Это и доказывает первое равенство в приведенной формуле.

4.3.

На плоскости провели n прямых общего положения (то есть никакие две из них не параллельны и никакие три не проходят через одну точку). Сколько получилось треугольников со сторонами на этих прямых?

Ответ Решение

Ответ. C3n· (n − 1)/2.

Решение.

Сначала подсчитаем количество точек пересечения этих прямых. Общность положения означает, что любые две прямые пересекаются ровно в одной точке. То есть на каждой прямой лежит (n-1) точка пересечения. Всего точек будет ^{n· (n − 1)}/₂, так как прямых n штук, и каждую точку мы считаем два раза — по одному разу для каждой прямой, на которой она лежит (вспомните, к примеру, задачу №5 Занятия 1).

Теперь заметим, что количество трегольников со сторонами на этих прямых в точности равно числу способов выбрать три точки из n· (n − 1)/2 неупорядоченным образом. Действительно, любые три точки пересечения наших прямых служат вершинами треугольника, так как любые две точки соединены прямой (в силу общности положения прямых). Наоборот, любой треугольник со сторонами на наших прямых будет иметь вершины в точках пересечения прямых. Поэтому число таких треугольников равно C3n· (n − 1)/2.

4.4.

Сколькими способами можно поставить на шахматную доску

а)

8 ладей?

b)

4 чёрных и 4 белых фигуры: коня, слона, ладью и ферзя?

Ответ Решение

Ответ. a) С₈⁶⁴; b) A₈⁶⁴.

Решение.

a) Чтобы расставить восемь ладей на доске, нужно выбрать восемь полей из 64, на которых ладьи будут стоять. Поскольку ладьи друг от друга не отличаются, порядок выбора этих полей неважен. Значит, искомое число равно С₈⁶⁴.

b) Этот случай отличается от предыдущего тем, что все фигуры различны между собой, и значит, важен порядок выбора полей. Искомое число способов, тем самым, равно A₈⁶⁴.

Сочетания с повторениям

4.5.

В буфете МГУ продаются пирожки пяти типов: с картошкой, с капустой, с мясом, с рисом и с яблоком. Сколькими способами можно купить восемь пирожков?

Ответ Решение

Ответ. Это можно сделать 495 способами.

Решение.

Пусть пирожки разных типов разложены на пяти лотках. Когда мы покупаем пирожки, мы действуем так: сначала берем сколько-то пирожков с картошкой (может быть, ни одного), затем переходим к лотку с пирожками с капустой и берем сколько-то пирожков оттуда, и так далее до тех пор, пока не наберем восемь пирожков.

Последовательность наших действий при этом можно описать так. Запишем в ряд восемь единиц. Отсчитаем от начала столько единиц, сколько пирожков с картошкой мы взяли, и поставим после них вертикальную черту. В частности, если мы не взяли ни одного пирожка с картошкой, поставим черту перед первой единицей, а если мы их взяли сразу восемь, поставим ее после последней единицы. Далее проделаем то же самое по отношению к пирожкам с капустой, с мясом, с рисом и с яблоком. Если в какой-то момент мы наберем восемь пирожков, а до последнего лотка еще не дойдем, оставшиеся вертикальные черточки будем в нужном количестве ставить после последней единицы. Если, наоборот, мы ничего не возьмем с первых нескольких лотков, черточки будем ставить перед первой единицей.

Всего в нашей записи будет 8 единиц и четыре вертикальные черты, то есть 12 символов. Чтобы получить произвольную запись такого вида, нужно выбрать 8 позиций из 12, на которые мы поставим единицы, а на остальные позиции поставить вертикальные черточки. Тем самым количество возможных способов купить восемь пирожков равно C⁸₁₂ = 495 (примените формулу из задачи 4.2).

4.6.

Покажите, что C_n^k = C^k_n+k-1.

Решение

Решение. Проведем рассуждения аналогично тому, как мы это делали при решении предыдущей задачи. Представим, что у нас есть n корзин с элементами различных типов, и робот, который должен набрать из этих корзин k каких-нибудь элементов. Для этого он будет брать сколько-то элементов из очередной корзины, а затем двигаться к следующей корзине. Последовательность его действий опишем последовательностью из единиц и вертикальных черточек. Сначала запишем в ряд столько единиц, сколько элементов робот возьмет из первой корзины (возможно, единиц вовсе не будет), а после них поставим черту. Затем припишем после черты столько единиц, сколько элементов будет взято из второй корзины, и после них также поставим черту, и так далее. Всего в нашей записи будет k единиц и (n-1) вертикальных черточек, то есть (n+k-1) символ. Чтобы получить произвольную запись такого вида, нужно из (n+k-1) позиций выбрать k позиций для единиц, а остальные позиции заполнить черточками. Количество способов сделать это равно C^k_n+k-1.

4.7.

Сколькими способами можно распределить 10 пятиклассников, 11 шестиклассников, 8 семиклассников и 12 восьмиклассников по пяти лифтам (считается, что лифты неограниченной вместимости, а школьники одного класса между собой не различаются)?

Ответ Решение

Ответ. C⁴₁₄·C⁴₁₅·C⁴₁₂·C⁴₁₆ способов.

Решение.

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

Присвоим лифтам номера от 1 до 5. Каждый способ распределить по лифтам пятиклассников будем записывать так: сначала пишем в ряд столько единиц, сколько пятитклассников посадим в первый лифт, затем ставим вертикальную черту и пишем еще столько единиц, сколько пятитклассников посадим во второй лифт, и так далее. Число таких записей равно числу способов распределить по лифтам пятиклассников и равно в точности C⁴₁₄ (вспомните предыдущие задачи). Для шестиклассников аналогичным образом получим C⁴₁₅ способов, для семиклассников C⁴₁₂ и наконец, для восьмиклассников C⁴₁₆ способов. Теперь все эти числа надо перемножить.

Замечание. При решении этой задачи мы фактически заново доказывали формулу для C_n^k. Решите эту задачу другим способом, непосредственно применяя эту формулу.

Разные задачи

4.8.

При передаче сообщений по телеграфу используется код Морзе. В этом коде буквы обозначаются набором точек и тире, причём количество используемых знаков может быть разным. Хватит ли трех точек и трех тире для того, чтобы зашифровать все русские буквы?

Ответ Решение

Ответ. Хватит.

Решение.

При решении задачи 3.11 мы подсчитали, что число кодов, состоящих из не более чем четырех символов азбуки Морзе, равно 30. Среди этих кодов есть только два, которые используют более трех однотипных символов: это, соответсвенно, код из четырех точек и код из четырех тире. Все остальные коды нам подходят. Тем самым у нас уже есть 28 «хороших» кодов. Осталось придумать еще пять кодов, удовлетворяющих нашим требованиям. Например, таких: — — — · ·, · — — — ·, · — · — ·,— · — · —, — — — · · ·. Теперь у нас есть 33 «хороших» кода, и мы можем ими зашифровать весь русский алфавит.

Попробуйте самостоятельно сосчитать количество всех «хороших» кодов. Хватит ли их, чтобы зашифровать сначала русские буквы, а потом латинские? А цифры?

4.9.

На прямой отмечено 10 точек, а на параллельной ей прямой — 11 точек. Сколько существует

а)

треугольников,

б)

четырёхугольников с вершинами в этих точках?

Ответ Решение

Ответ. a) 1045; b) C₁₀²·C₁₁² = 2475.

Решение.

a) Число треугольников с вершинами в этих точках равно числу способов выбрать две точки на одной прямой и одну — на другой. При этом пару точек, лежащих на одной из прямых, нужно выбирать неупорядченным образом: при их перестановке треугольник не изменится. Если одну вершину выбирать на первой прямой, а еще две на второй, то получится 10·C₁₁² = 550 различных треугольников (10 способов выбрать вершину на первой прямой и C₁₀² = 55 способов выбрать две вершины на второй прямой). Аналогично найдем, что если на первой прямой брать две вершины, а на второй — только одну, получится 11·C₁₀² = 495 различных треугольников. Значит, всего треугольников с вершинами в отмеченных точках существует 550+495 = 1045.

b) Для построения четырехугольника надо выбрать по две точки на каждой прямой (иначе получится не четырехугольник, а треугольник или даже отрезок). При этом та точка, которая лежит левее на первой прямой, будет соединяться стороной с точкой, лежащей левее на второй прямой (и то же самое касается точек, которые лежат правее), иначе получится фигура, которую мы четырехугольником не считаем (попробуйте нарисовать такую фигуру). Поэтому пары точек на каждой прямой надо выбирать неупордоченным образом, а затем вершины соединять вышеуказанным способом. Всего есть C₁₀² = 45 способов выбрать пару точек на первой прямой и C₁₁² = 55 способов выбрать пару точек на второй прямой. Количество искомых четырехугольников равно произведению этих чисел, а именно 2475.

4.10.

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

Ответ Решение

Ответ. А₂₀⁵ = 1860480.

Решение. Сначала сосчитаем количество всевозможных различных компаний из трех человек. Оно, как нетрудно сообразить, равно С₆³ = 20 (примените формулу из задачи 4.2 самостоятельно). Теперь из этих возможных компаний нужно (упорядоченным образом) выбрать пять, чтобы последовательно приглашать их в гости. Это можно сделать А₂₀⁵ = 1860480 способами (примените формулу из «Теоретических сведений»).

4.11.

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

Решение

Решение.

Выберем какого-нибудь человека из нашей компании (назовем его А). Тогда в компании либо есть трое, которые с ним знакомы, либо трое, которые с ним незнакомы. Этих троих назовем Б, В, Г.

Пусть сначала Б, В, Г знакомы с А. Если среди них есть двое знакомых друг с другом, то эти двое и А знакомы между собой, и утверждение задачи выполнено. Если же среди них нет знакомых, то они и есть те трое, которые друг с другом не знакомы, и утверждение вновь выполнено. Случай, когда Б, В и Г не знакомы с А, рассматривается точно так же, только слова «знакомы» и «не знакомы» меняются местами.