Rukovodstvo_po_resheniju_zadach

в) остался один случай, когда цифры, кратные двум, занимают три первых места, а последнее место занимает цифра, кратная трём: 3·42·3 = 144.

Сложим полученные частные результаты: 81 + 108 + 144 = 333.

Ответ: 333.

Пример 2. Десятизначное двоичное число b (условимся называть его b-числом) разделили на две части: число b1 шестизначное (b1-число) b2 – четырёхзначное (b2-число). Сколько существует двоичных b-чисел, для каждого из которых выполняется условие: в числе b1 столько же единиц, сколько и в числе b2?

Решение. Всего необходимо рассмотреть пять частных случаев:

а) в обоих числах нет единиц. Такое десятизначное b-число существует только одно. Оно состоит из последовательности десяти нулей;

б) в обоих числах b1 и b2 содержится по одной единице. Существует 6 b1-чисел, каждое из которых представляет собой шестизначное двоичное число, содержащее одну единицу и пять ну-

лей: 000001, 000010, 000100, 001000, 010000, 100000. Для b2 существует четыре числа: 0001, 0010, 0100, 1000. По правилу произведения: количество искомых b-чисел равно 6·4 = 24;

в) в числах b1 и b2 содержится точно по две единицы. Существует C62 15 b1-чисел, где каждое из них представляет собой двоичное шестизначное число, содержащее две единицы и че-

тыре нуля. Существует C42 6 b2-чисел, т.е. четырёхзначных чисел, содержащих две единицы и два нуля каждое. По правилу произведения искомое количество b-чисел равно 15·6 = 90;

г) в числах b1 и b2 содержится точно по три единицы. Рассуждая, как и в предыдущих случаях, находим, что искомое количество b-чисел равно

C63 C43 20 4 80;

д) в числах b1 и b2 содержится точно по четыре единицы. Тогда C64 C44 15 1 15. Просуммируем все эти частные результаты: 1 + 24 + 90 + 80 + 15 = 210.

Ответ: 210.

Пример 3. Сколько существует чётных трёхзначных чисел пятеричной системы счисления, если числа могут начинаться с нуля, и в каждом числе возможны повторы цифр? Например: 012, 224, 110 и др.

Решение. В последовательности натуральных чисел, представленных в пятеричной системе, чётные и нечётные числа чередуются, начиная с числа 000, которое является чётным, и кончая числом 444, которое также является чётным. Следовательно, чётных пятеричных чисел на единицу больше, чем нечётных. По формуле числа размещений с повторениями находим, что всего существует 53 = 125 трёхзначных пятеричных чисел. Отсюда вывод: существует 62 нечётных трёхзначных пятеричных числа и 63 – чётных.

Ответ: 63.

Пример 4. Из цифр множества {1, 2, 3, 4, 5, 6, 7} выбирают четыре цифры и записывают ими семизначное число. Сколько возможно таких чисел, если одна из выбранных четырёх цифр входит в семизначное число точно четыре раза, а все остальные – по одному разу? Например, если выбрали цифры 2, 3, 6, 7 то искомыми являются числа 2222376, 7727637, 6663267 и т.д.

Решение. Пусть выбранными являются цифры 1, 2, 3, 4. Рассмотрим частные случаи.

Сначала предположим, что повторяется цифра 1. Одно из чисел имеет вид 1111234. Все остальные числа с повтором цифры 1 могут быть получены перестановкой цифр этого числа. Количество таких чисел находим по формуле числа перестановок с повторениями

		7!		210.
P7		4! 1! 1! 1!

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

Если выберем другие четыре цифры, то получим ещё 840 чисел. Из семи цифр четыре можно выбрать

n(n 1)(n 2) 2 3 2925.

C4			7!		35
7	(7		4)! 4!

способами. Таким образом, всего искомых чисел существует 840·35 = 29400.

Ответ: 29400.

Пример 5. Сколько существует 15-значных двоичных чисел, в каждом из которых содержится точно четыре единицы, причём эти единицы нигде рядом не стоят? Числа могут начинаться с нуля.

Решение. В 15-значном двоичном числе, содержащем четыре единицы, имеется 11 нулей. Запишем эти нули в ряд, поставив между нулями, а также слева и справа от них по одной точке:

.0.0.0.0.0.0.0.0.0.0.0.

Если выберем какие-либо четыре точки и заменим их единицами, то получим 15-значное число, в котором не будет рядом стоящих единиц. Всего точек 12. Следовательно, выбрать четыре из них можно

C 4			12!			9 10 11 12	495
12	(12		4)! 4!			1 2 3 4

способами. Столько же существует искомых чисел.

Ответ: 495.

Пример 6.

Известно, что существует 2925 n-значных двоичных чисел, в каждом из которых содержится точно три единицы (и соответственно n – 3 нулей). Числа могут начинаться с нуля. Требуется найти n. Решение. Запишем условие с применением формулы числа сочетаний (без повторений) из n элементов по 3:

C3		n!
n		(n 3)! 3!

Сократим дробь на (n – 3)!:

n(n 1)(n 2)

1 2 3

2925.

2925.

Умножив левую и правую части на 6, получаем уравнение:

Это уравнение третьей степени. Его можно решить с применением формул Кардано. Однако в данном случае решение можно найти другим, более простым путём. Левая часть полученного уравнения – это произведение трёх натуральных чисел, из которых большее число отличается от среднего на единицу и среднее отличается от меньшего также на единицу, т.е. они идут непосредственно один за другим в последовательности натурального ряда. Следовательно, задача сводится к тому, чтобы правую часть представить в виде произведения трёх таких чисел.

Разложим число 2925 на простые множители: 2925 = 3 3 5 5 13.

Тогда уравнение примет вид

n(n 1)(n 2) 2 3 3 3 5 5 13.

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

ствами:

2 3 3 3 5 513 (3 3 3) (2 13) (5 5) 27 26 25.

Подставим этот результат в уравнение: n(n 1)(n 2) 27 26 25. Отсюда непосредственно следует, что n = 27.

Ответ: 27.

Пример 7. Из алфавита выбрали семь различных букв и каждую из них записали на отдельной карточке. Из карточек составляют 4-буквенные слова. Сколько существует таких слов, буквы в которых идут в алфавитном порядке?

Решение. Расположим все карточки в алфавитном порядке. Тогда любые 4 карточки, если не менять их порядок, дадут искомое слово. Всего таких выборок:

	C 4	7!			5 6 7	30.
		(7 4)!4!			1 2 3
	7

Ответ: 30.

Кроме правила произведения в комбинаторике широко применяется правило суммы, известное также под названием принципа включения-исключения. Пусть даны множества Р1 и Р2. Если

Р1 Р2 = , то |Р1 Р2| = |Р1| + |Р2|,

т.е. если элемент первого множества может быть выбран |Р1| способами, а элемент второго множества – |Р2| способами, то выбор «либо элемент множества Р1, либо элемент множества Р2» может быть осуществлен |Р1| + |Р2| способами.

Пример 8. В тарелке 7 яблок и 5 груш. Сколькими способами можно выбрать один плод? Решение. Если Р1 – множество яблок, Р2 – множество груш, то:

|Р1| + |Р2| = 7 + 5 = 12.

Ответ: 12.

Если же Р1 Р2 Ø (т.е. множества Р1 и Р2 имеют общие элементы) то правило суммы записывается в виде более сложной формулы:

|Р1 Р2| = |Р1| + |Р2| – |Р1 Р2|.

Пример 9. Даны множества: Р1 = {1, 2, 4, 7, 9}; Р2 = { 1, 4, 5, 6, 8}.

Сколько элементов во множестве Р1 Р2?

Решение. По правилу суммы |Р1 Р2| = 5 + 5 – 2 = 8.

Ответ: 8.

В случае трех множеств правило суммы записывается в виде

|Р1 Р2 Р3| = |Р1 Р2| + |Р3| – |(Р1 Р2) Р3| = = |Р1| + |Р2| – |Р1 Р2| + |Р3| – |Р1 Р3 Р2 Р3| =

=|Р1| + |Р2| – |Р1 Р2| + |Р3| – (|Р1 Р3| + |Р2 Р3| – |Р1 Р2 Р3|)=

=|Р1| + |Р2| + |Р3| – |Р1 Р2| – |Р1 Р3| – |Р2 Р3| + |Р1 Р2 Р3|.

Для четырех множеств получаем аналогично:

|Р1 Р2 Р3 Р4| = |Р1| + |Р2| + |Р3| + |Р4| –

– |Р1 Р2| – |Р1 Р3| – |Р1 Р4| – |Р2 Р3| – |Р2 Р4| – |Р3 Р4| +

+|Р1 Р2 Р3| + |Р1 Р2 Р4| + |Р1 Р3 Р4| + |Р2 Р3 Р4| –

–|Р1 Р2 Р3 Р4|.

Пример 10. Из 100 студентов английский язык знают 28 человек, немецкий – 30, французский – 42, английский и немецкий – 8, английский и французский – 10, немецкий и французский – 5, все три языка знают 3 человека. Сколько студентов не знают ни одного из этих трех иностран-

ных языков [21, с. 15]?
Решение. Обозначим:
|Р1| – число студентов, знающих английский язык;
|Р2| – число студентов, знающих немецкий язык;
|Р3| – число студентов, знающих французский язык.
Согласно условию:	|P1| = 28;	|P2| = 30;	|P3| = 42.

|Р1 Р2| = 8 – число студентов, знающих два языка – английский и немецкий; |Р1 Р3| = 10 – число студентов, знающих два языка – английский и французский; |Р2 Р3| = 5 – число студентов, знающих два языка – немецкий и французский;

|Р1 Р2 Р3| = 3 – число студентов, знающих три языка. По правилу суммы:

|Р1 Р2 Р3| = 28 + 30 + 42 – 8 – 10 – 5 + 3 = 80.

Таким образом, знают хотя бы один иностранный язык 80 студентов, а ни одного иностранного языка не знают 20 человек.

Ответ: 20

13.2. Комбинаторика в теории вероятностей

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

Например, пусть монету подбрасывают два раза. Вероятность того, что оба раза выпадет герб, равна 1/4. Здесь знаменатель равен 4. Столько всего существует исходов эксперимента, когда монету подбрасывают два раза: ГГ, ГЦ, ЦГ, ЦЦ, где буквой Г обозначено падение монеты гербом вверх, а Ц – падение монеты цифрой вверх. Числитель равен 1, так как существует только один исход эксперимента, когда оба раза монета упадёт гербом вверх.

Если рассматривается два случайных события A1 и A2, и требуется найти вероятность того, что состоятся они оба, то сначала необходимо определить вероятности каждого из событий, а затем найти их произведение. При этом необходимо различать зависимые и независимые события.

Если события независимы, то вероятность их произведения определяется по формуле

P(A1 ·A2) = P(A1)·P(A2),

а в случае n случайных событий A1, A2, A3,…, An:

P(A1 ·A2·A3·,…, ·An) = P(A1)·P(A2)·P(A3) ·…·P(An).

Если же события A1 и A2 являются зависимыми, то говорят об условной вероятности:

P(A1 ·A2) = P(A1)·P(A2/A1),

где P(A2/A1) – условная вероятность, т.е. вероятность события A2 при условии, что событие A1 состоялось.

Например, пусть в урне находятся 4 белых шара и 3 чёрных. Наугад вынимают один шар (событие A1), записывают его цвет, шар возвращают в урну и снова наугад вынимают один шар (событие A2). Какова вероятность того, что в обоих случаях будут вынуты только чёрные шары?

Эти события независимы. Вероятность того, что первый шар будет чёрным, равна: P(A1) = 3/7. Вероятность того, что и второй шар будет чёрным, также равна P(A2) = 3/7. Следовательно, искомая вероятность равна P(A1 A2) = 9/49.

Изменим условие эксперимента: из урны вынимают один шар (событие A1), после чего не возвращая его в урну, наугад вынимают второй шар (событие A2). Какова вероятность того, что оба вынутых шара будут чёрными? Очевидно, что при первом извлечении вероятность вынуть чёрный шар равна P(A1) =3/7. Так как шар не возвращается в урну, то теперь в ней не 7 шаров, а только 6. Кроме того, состоялось событие: вынут чёрный шар. Следовательно, в урне осталось два чёрных шара и условная вероятность вынуть чёрный шар равна: P(A2/A1),) = 2/6. После сокращения P(A2/A1),) = 1/3. Искомая вероятность равна:

3 1 1 .

P(A1)·P(A2 / A1) = 7 3 7

Рассмотрим ещё ряд примеров.

Пример 1. Игральную кость подбрасывают 2 раза. Найти вероятность того, что второе выпавшее число будет в 2 раза больше первого (грани пронумерованы: 1, 2, 3, 4, 5, 6).

Решение. Первый бросок может закончиться шестью исходами, и второй шестью. Следовательно, число всех исходов равно 36. Это знаменатель искомой вероятности. Числитель равен 3. Это исходы 1 и 2, 2 и 4, 3 и 6. Искомая вероятность равна 1/12.

Ответ: 1/12.

Пример 2. Некто задумал двузначное десятичное число N (с нуля двузначные числа не начинается). Найти вероятность того, что если каждую цифру представить в двоичном коде 8421, то в восьмизначном двоично-десятичном коде будет точно две единицы.

Решение. Знаменатель искомой вероятности равен 90 – столько существует двузначных десятичных чисел, не начинающихся с нуля. Это числа 10, 11, 12, ..., 99.

Определим числитель. В двоично-десятичном коде каждая десятичная цифра заменяется тетрадой – четырехзначным двоичным кодом. Например: 35|10 = 00110101|2-10, где 35|10 – десятичная запись числа 35, а 00110101|2-10 – двоично-десятичное изображение того же числа. Здесь десятичная цифра 3 заменена тетрадой 0011, а цифра 5 – тетрадой 0101.

Если две единицы находятся в первой тетраде, то во второй их нет (так как во всём коде должно быть 2 единицы). Всего существует шесть тетрад с двумя единицами. Четырьмя из них кодируются цифры 3, 5, 6 и 9, следовательно, существует четыре двоично-десятичных кода, окан-

чивающихся четырьмя нулями: 00110000, 01010000, 01100000, 10010000.

Если в первой тетраде одна единица, то и во второй одна. Это тетрады вида: 0001, 0010, 0100, 1000. Из них можно составить 16 двоично-десятичных кодов:

00010001, 00100001, 01000001, 10000001, 00010010, 00100010, 01000010, 10000010, 00010100, 00100100, 01000100, 10000100, 00011000, 00101000, 01001000, 10001000.

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

Таким образом, всего существует 20 двоично-десятичных кодов, в каждом из которых точно две единицы. Искомая вероятность равна 20/90. После сокращения: 2/9.

Ответ: 2/9.

Пример 3. Некто задумал двузначное десятичное число N (с нуля двузначные числа не начинается). Найти вероятность того, что в задуманном числе нет ни одной цифры 5. Повторы цифр возможны.

Решение. Существует 90 двузначных десятичных чисел, не начинающихся с нуля. Среди них 18 чисел содержат хотя бы одну цифру 5. Это числа:

15, 25, 35, 45, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 65, 75, 85, 95.

Следовательно, всего существует 90 – 18 = 72 числа, в каждом из которых нет ни одной цифры 5. Таким образом, искомая вероятность равна: 72/90. После сокращения: 4/5.

Ответ: 4/5.

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

Решение. Пронумеруем мишени цифрами троичной системы 0, 1, 2, и закодируем исходы выбора мишеней пятизначными троичными числами, где каждому троичному разряду соответствует один из стрелков. Например, код 10021 обозначает: первый стрелок выбрал первую мишень, второй и третий – нулевую, четвертый – вторую, пятый – первую. Всего существует 35 = 243 пятизначных троичных кодов, которые могут начинаться с нуля. Столько же существует и вариантов выбора мишеней. Это знаменатель искомой вероятности.

Определим числитель. Существует только три варианта выбора мишеней, когда поражена одна мишень из трех. Это коды: 00000 – все пули попали в нулевую мишень, 11111 – все пули попали в первую мишень, 22222 – все пули попали во вторую мишень. Искомая вероятность равна 3/243. После сокращения на 3 получаем 1/81.

Ответ: 1/81.

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

Как и в предыдущем примере пронумеруем мишени: 0, 1, 2, 3, и закодируем все варианты выбора мишеней 5-значными числами четверичной системы счисления. Всего существует 45 = 1024 пятизначных четверичных кодов, которые могут начинаться с нуля. Столько же существует и вариантов выбора мишеней. Это знаменатель искомой вероятности.

Определим числитель. Сначала предположим, что будут поражены мишени с номерами 0 и 1. Этому соответствуют пятизначные двоичные коды, в каждом из которых содержится хотя бы один нуль и хотя бы одна единица. Число таких кодов равно 30, так как всего существует 32 пятизначных двоичных числа, среди которых код 00000 не содержит единиц, а код 11111 не содержит нулей, а все остальные коды содержат и нули и единицы. Если предположить, что поражёнными будут другие две мишени, то и в этом случае возможно 30 вариантов выбора мишеней. Все-

С2		4!	6
4		2! 2!
го возможно				случаев, когда пораженными являются точно две мишени из четырёх.

Следовательно, числитель равен: 30·6 = 180. Тогда искомая вероятность равна 180/1024. После сокращения на 4 получаем: 45/256. Ответ: 45/256.

Пример 6. В урне 4 белых и 8 черных шаров. Найти вероятность того, что если наугад извлечь 4 шара, то два из них будут белыми и два черными.

Решение. Всего шаров 12. Из них 4 шара можно выбрать

С4		12!			9 10 11 12	495
12		8! 4!			1 2 3 4

способами. Это знаменатель искомой вероятности.

Для выбора двух черных шаров из восьми существует С82 28 вариантов. Выбор двух бе-

лых шаров из четырех возможен С42 6 способами. Тогда искомая вероятность равна:

p 28 6 56 . 495 165

Ответ: 56/165.

Пример 7. Ребенок, не умеющий читать, рассыпал составленное из букв разрезной азбуки слово «искусство», выбрал из них четыре карточки и расположил их в один ряд. Найти вероятность того, что у него получится слово «куст».

Решение. Рассмотрим четыре события: A – выбрана буква «к», B – выбрана буква «у», C – выбрана буква «с», D – выбрана буква «т». Найдем их вероятности. Вероятность события A равна: p(A) = 1/9. Так как событие A состоялось, то среди рассыпанных осталось 8 карточек. Следовательно, вероятность события B равна: p(B) = 1/8. Теперь осталось 7 карточек, поэтому вероятность события C равна: p(C) = 3/7. Осталось 6 карточек. Вероятность события D равна: p(D) = 1/6. По правилу произведения вероятностей получаем:

	p	1		1		3		1			1	.
		9		8		7		6		1008

Ответ: 1/1008.

Пример 8. Из колоды, в которой 36 карт, наугад вынимают две карты. Найти вероятность того, что обе они будут пиковой масти.

Решение. Две карты из 36 можно извлечь С362 630 способами. Знаменатель найден.

Пиковой масти в колоде 9 карт. Две из них можно извлечь С92 36 способами. Искомая вероятность равна 36/630. После сокращения получаем p = 2/35. Ответ: 2/35.

Пример 9. Некто задумал 10-значное двоичное число (числа могут начинаться с нуля). Найти вероятность того, что в числе содержится хотя бы один нуль и хотя бы одна единица. Решение. Всего возможно 1024 десятизначных двоичных чисел. Существует одно число, состоящее из десяти нулей, и одно число, состоящее из десяти единиц. Во всех остальных 1022 числах содержится хотя бы один нуль и хотя бы одна единица. Следовательно, искомая вероятность равна p = 1022/1024. После сокращения на 2: p = 511/512. Ответ: 511/512.

Пример 10. В инструментальный ящик положили 14 напильников. Из них 7 круглых, 3 плоских и 4 треугольных. Из ящика наугад берут 4 напильника. Найти вероятность того, что среди них хотя бы два напильника будут круглыми.

Решение. Четыре напильника из 14 можно выбрать						С 4
						14 способами. Это знаменатель искомой ве-
роятности, равный
С4		14!			11 12 13 14	7 11 13 1001.
14	10! 4!				1 2 3 4

Переходим к числителю. Условие «хотя бы два» говорит о том, что в выборке будет два напильника, либо три, либо четыре.

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

С2		7!			6 7	21
7		5! 2!			1 2

способом. Кроме того, к каждой паре круглых напильников надо добавить по два напильника из некруглых. Число некруглых напильников равно 7 (так как в ящике 3 плоских напильника и 4 треугольных). Выбрать два из них можно также 21 способами. Следовательно, одна составляющая числителя, соответствующая выборке двух круглых (и двух некруглых) напильников, равна 21·21

= 441.

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

С3		7!			5 6 7	35
7		4! 3!			1 2 3

вариантов выбора трёх круглых напильников из семи. К каждой тройке круглых напильников необходимо добавить по одному из некруглых. Следовательно, вторая составляющая числителя, соответствующая выбору трёх круглых напильников (и одного некруглого), равна 35·7 = 245.

Остался один случай, когда все напильники в выборке являются круглыми. Число таких

выборок равно С74 35.

Просуммируем полученные три числа: 441 + 245 + 35 = 721. Искомая вероятность равна 721/1001. После сокращения получаем: 103/143.

Ответ: 103/143.

Пример 11. Каждая из 33 букв русского алфавита записана на отдельной карточке. Из этих 33 букв наугад выбирают три. (Среди 33 букв русского алфавита 10 букв являются гласными, 21 – согласными, твёрдый и мягкий знаки не являются ни гласными, ни согласными.) Найти вероятность того, что на выбранных трёх карточках гласных букв будет больше чем согласных и будут отсутствовать твёрдый и мягкий знаки.

Решение. Знаменатель равен

С3		33!			31 32 33	31 16 11 5456.
33		30! 3!			1 2 3

Числитель состоит из двух слагаемых:

а) в выборке три гласных буквы (согласных букв нет). Число выборок, состоящих только из

С3		10!			8 9 10	120;
10		7! 3!			1 2 3
гласных букв, равно

б) в выборке одна согласная буква (существует C211 21 вариант её выбора) и две гласные

буквы (число вариантов их выбора равно C102 45). Следовательно, второе слагаемое числителя равно 21·45 = 945.

Сумма чисел 120 и 945 есть числитель искомой вероятности, равной

120 945 1065 .

5456 5456

Ответ: 1065/5456.