Комбинаторика. Решение комбинированных задач

Комбинаторика. Комбинированные задачи

1. Шесть граней игрального кубика помечены цифрами 1, 2, 3, 4, 5, 6. Кубик бросают дважды и записывают вы­падающие цифры.

а) Найдите число всех возможных вариантов.

б) Укажите те из них, в которых произведение выпавших чисел кратно 10.

в) Составьте таблицу из двух строк. В первой строке запишите суммы выпавших очков, во второй - количество вариантов, в кото­рых выпадает эта сумма.

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

Решение.

а) При первом бросании кубика может выпасть любая из 6 цифр, после этого при втором бросании - тоже любая из 6 цифр; по правилу произведения число возможных вариантов равно 6 • 6 = 36.

б) Произведение выпавших чисел кратно 10 при следующих вариантах:

2 - 5, 5 - 2, 4 - 5, 5 - 4, 5 - 6, 6 - 5. Таких вариантов 6.

в)

Сумма выпав­ших очков	2	3	4	5	6	7	8	9	10	11	12
Количество вариантов	1	2	3	4	5	6	5	4	3	2	1

1-1 1-2 1-3 1-4 1-5 1-6 2-6 3-6 4-6 5-6 6-6

2-1 2-2 2-3 2-4 2-5 3-5 4-5 5-5 6-5

3-1 3-2 3-3 3-4 4-4 5-4 6-4

4-1 4-2 4-3 5-3 6-3

5-1 5-2 6-2

6-1

Модуль разности	0	1	2	3	4	5
Количество результатов	6	10	8	6	4	2

г)

Ответ: а) 36; б) 6.

2. В шахматном кружке занимаются 16 человек. Сколькими способами тренер может выбрать из них для предстоя­щего турнира:

а) команду из четырех человек;

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

Решение.

а) Выбираем 4 шахматистов из 16 без указания порядка; коли­чество способов = 1 820 способов.

б) Выбираем 4 шахматистов из 16 с указанием порядка их расположения в команде; количество способов

А = 16-15-14-13 = 43 680 способов.

Ответ: а) 1 820 способов; б) 43 680 способов.

3. Из цифр 1, 2, 3, 4, 5 составили все возможные трехзначные числа (без повторения цифр). Сколько среди них таких, которые: а) кратны 2; б) кратны 3?

Решение.

Выбираем из 5 цифр три (без повторений), причем порядок вы бора имеет значение (123 и 312 - разные числа).

а) Составленное трехзначное число кратно 2, если оно оканчивается 2 или 4. Фиксируем 2, количество чисел равно А= 4-3 = 12. Фиксируем 4, количество чисел равно А= 4-3 = 12.

По комбинаторному правилу суммы количество чисел, крат­ных 2, равно:

А+ А=2 А=

б) Составленное трехзначное число кратно 3, если сумма со­ставляющих его цифр делится на 3. Из пяти цифр можно составить
С =С=С троек цифр, отличающихся хотя бы одной цифрой.
Чтобы определить, сколько среди этих троек таких, сумма которых
делится на 3, составим все эти сочетания и для каждого из них най­дем сумму цифр (метод полного перебора):

123 234 345

124 235

125 245

134

135

Из С = 10 полученных наборов только четыре набора дают в сумме число, кратное 3: 123, 135, 234, 345.

Каждый из четырех полученных наборов цифр порождает Р₃= 3! = 6 различных чисел (всевозможные перестановки из трех цифр), поэтому количество трехзначных чисел, кратных 3, которые можно составить из пяти данных цифр, равно 4 • Р₃ = 4 3! = 4 6 = 24.

Ответ: а) 24 числа; б) 24 числа.

4. Сколькими способами из класса, где учатся I учащихся, можно выбрать: а) двух дежурных; б) старосту и помощника старосты?

Решение.

а) При выборе двух дежурных порядок выбора не имеет значения (дежурные неразличимы), поэтому общее количество способов выбора равно

б) При выборе старосты и помощника порядок выбора имеет значение (Иванов - староста, Петров - помощник и Петров - ста­роста, Иванов - помощник - это разные выборы), поэтому общее количество способов выбора равно А = 2423 = 552.

Ответ: а) 276; б) 552.

5. Из цифр 1, 2, 3, 4, 5 составили все возможные трехзначные числа (с повторением цифр). Сколько среди них та­ких, сумма цифр которых равна: а) 3; б) 4; в) 6?

Решение.

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

После этого в каждой тройке сделаем все возможные переста­новки и найдем общее число трехзначных чисел с данной суммой Цифр (по правилу суммы).

а) Сумма цифр равна 3. Такую сумму имеет единственный трехзначный набор 111, в котором перестановки невозможны, т. к. все три цифры одинаковые. В этом случае получаем 1 число.

б) Сумма цифр равна 4. Такую сумму имеет единственный трехзначный набор 112, но в этом наборе возможны 3 перестановки 2 может стоять на первом, втором или третьем месте). В этом случае получаем 3 числа.

в) Сумма цифр равна 6. Такую сумму имеют следующие трехзначные наборы: 114; 123 и 222.

В первом наборе возможны 3 перестановки, во втором – Р₃=3!=6 перестановок, в третьем - ни одной. По правилу суммы в этом случае получаем 3 + 6+1 = 10 различных чисел.

Ответ: а) 1; б) 3; в) 10 чисел.

6. Из цифр 0, 1,2, 3, 4, 5 составили все возможные трехзначные числа (без повторения цифр). Сколько среди них та­ких, сумма цифр которых равна: а) 6; б) 9?

Решение.

Сначала составим все возможные наборы из трех цифр, входя­щих в перечень 0, 1,2, 3, 4, 5, сумма цифр в которых равна соот­ветственно 6 или 9 (повторение цифр не допускается; ноль не мо­жет стоять на первом месте).

После этого в каждой тройке сделаем всевозможные переста­новки и найдем общее число трехзначных чисел с данной суммой цифр (по правилу суммы).

а) Сумма цифр равна 6. Такую сумму имеют следующие трех­значные наборы: 510; 420; 321.

В первом наборе возможны 221=4 перестановки, во втором также 2 • 2 • 1 = 4 перестановки, в третьем – Р₃= 3! =6 перестано­вок. По правилу суммы в этом случае получаем 4 + 4 + 6 = 14 раз­личных трехзначных чисел.

б) Сумма цифр равна 9. Такую сумму имеют следующие трех­значные наборы: 540; 531; 432.

В первом наборе возможны 2-2-1=4 перестановки (ноль не может стоять на первом месте), во втором и третьем наборах - по Р₃ = 3! = 6 перестановок. Общее количество трехзначных чисел с суммой цифр 9 по правилу суммы равно 4 + 6 + 6 = 16.

Ответ: а) 14 чисел; б) 16 чисел.

7. В Сети связь происходит через узлы, которые нумеруются восьмизначными номерами (номер, например» 00011122 возможен).

а) Сколько в Сети может быть узлов?

б) Сколько в Сети узлов с суммой цифр номера, равной 71?

в) Сколько в Сети узлов с суммой цифр номера меньше 3?

Решение.

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

а) При образовании номера в каждый из восьми разрядов мож­но выбрать любую из 10 цифр (от 0 до 9); общее число узлов по правилу произведения равно = 10⁸ = 100 000 000.

б) Максимальная сумма цифр в номере будет, если во всех восьми разрядах стоят 9; сумма цифр при этом равна 72. Сумма цифр будет 71, если в одном из разрядов стоит 8, а во всех осталь­
ных-9. Для размещения одной 8 в номере можно выбрать любое из восьми мест, поэтому количество узлов с суммой цифр номера 71 равно 8.

в) Сумма цифр номера меньше 3 - это или 0, или 1, или 2. Сумма цифр равна 0, если во всех восьми разрядах номера сто­ят нули; такой номер один. Сумма цифр равна 1, если в одном из восьми разрядов номера стоит единица, а во всех остальных - нули; таких номеров 8. Сумма цифр равна 2, если:

а) в одном из разрядов стоит 2, в остальных - нули; таких номеров 8;

б) в двух разрядах стоят 1, в остальных - нули. Для первой единицы можно выбрать одно из 8 мест, для второй - одно из 7 ос­тавшихся, всего будет 8-7 = 56 вариантов. Но при этом учитывается порядок расположения единиц (первая - в третьем разряде, вто­рая - в пятом, и наоборот, первая - в пятом разряде, вторая в третьем; однако оба таких варианта дают один номер: 00101000, по­скольку единицы неразличимы и их перестановка ничего не меняет в номере). Таким образом, количество разных номеров с двумя

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

( выбираем два места из восьми без учета порядка). Итак, общее количество номеров с суммой цифр меньше 3 равно: 1 +8+ (8+ 28) = 45.

Ответ: а) 100 000 000; б) 8; в) 45.

8. Вова услышал в песне, что «...у зим бывают имена...». Он вспомнил семь самых хороших зим своей жизни, на­писал семь женских имен и решил дать каждой вспомнившейся зиме женское имя из своего списка (всем - разное).

а) Сколькими способами он может это сделать?

б) Сколько способов существует, если первая зима – точно Татьяна, а последняя - несомненно, Анна?

в) Сколько способов существует, если женских имен восемь, а не семь?

Решение.

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

а) Присваивая каждой из семи зим одно из семи имен, мы осу­ществляем перестановки семи элементов (имен); число перестано­вок равно 7! = 1 -2-3-4-5-6-7 = 5040.Таким образом, семи зимам можно присвоить разные имена (из 7 отобранных) 5 040 разными способами.

б) Если два имени закреплены за двумя зимами, то остается пять зим, которым можно присваивать разные имена из пяти ос­тавшихся; количество вариантов равно числу перестановок из пяти элементов:5! = 1-2-3-4-5 = 120.

в) Если в списке имен для 7 зим будет не 7, а 8 имен, то количе­ство способов присвоения имен можно найти по правилу произве­дения: для первой зимы можно выбрать одно из 8 имен, для вто­рой - одно из 7 оставшихся, и т. д., для седьмой зимы - одно из оставшихся; общее число способов равно 8-7-6-5-4-3-2 = 40 320.

Если учащиеся знают формулу для числа размещений, то это число равно АI.

г) Если имен семь, а зим восемь, то, очевидно, нет ни одного способа присвоить каждой зиме свое имя, отличное от других. Ко­личество способов равно 0.

Ответ: а) 5 040; б) 120; в) 40 320; г) 0.

9. Ася помнит, что в ответе задачи на правило ум­ножения для двух испытаний получалось число 48 и что испытания с одним исходом не рассматривались. Ей надо вспомнить число исходов в обоих испытаниях.

а) Из скольких вариантов Асе придется выбирать правильный ответ?

б) Сколько из них вариантов, состоящих из чисел разной четно­сти?

в) Сколько из них вариантов, состоящих из чисел, которые от­личаются друг от друга более чем на 10?

г) А сколько всего вариантов, если испытаний было три?

Решение.

По правилу умножения общее число исходов двух испытаний, одно из которых имеет n₁ исходов, а второе – n₂ исходов, равно n₁ n₂. По условию задачи это произведение равно 48, т. е. n₁ n₂ = 48, и испытания с одним исходом не рассматривались, т. е. n₁ 1 и n₂ 1.

а) Количество вариантов, из которых придется выбирать все, равно количеству всевозможных пар чисел (с учетом их порядка в паре), произведение которых равно 48. Поскольку 48 = 2 • 2 2 • 2 • 3, то для n₁ можно выбрать одно из следующих значений: 2, 3, 4, 6, 8, 12, 16, 24. В результате можно составить следующие 8 вариан­тов произведений n₁ n₂ , которые учитывают и порядок множителей.

Таким образом, все придется выбирать из восьми указанных вариантов.

б) Среди 8 вариантов произведений только 2 варианта содержатся разной четности(3•1616•3).

в) Среди 8 вариантов произведений 4 варианта состоят из чисел, которые отличаются друг от друга более чем на 10: 2-24, 3- 16, 16-3, 24-2.

г) Если испытаний было 3, то n₁ При этом можно составить следующие произведения, отличающиеся хотя бы одним множителем (фиксируем первый элемент, последовательно увеличиваем второй, третьим произведение до 48)

Каждый из этих четырех наборов можно изменять, переставляя в нем множители. В первом наборе перестановка двоек ничего не дает, поэтому можно менять только место, на котором стоит 12. Получим 3 раз­ных набора множителей. Во втором и третьем наборах все множители разные, можно получить по 3! = 6 перестановок из каждого набора.

В четвертом наборе два элемента одинаковые, можно менять только месторасположение тройки; получаем 3 разных набора. Общее число вариантов при трех испытаниях равно: 3 + 6 + 6 + 3 = 18.

Ответ: а) 8; б) 2; в) 4; г) 18.

10. «Вороне как-то Бог послал кусочек сыра», брынзы, колбасы, сухарика и шоколада. «На ель Ворона взгромоз­дясь, позавтракать совсем уж было собралась, да призадумалась»:

а) если есть кусочки по очереди, то из скольких вариантов при­дется выбирать;

б) сколько получится «бутербродов» из двух кусочков;

в) если съесть сразу три кусочка, а остальные спрятать, то из скольких вариантов придется выбирать;

г) сколько получится вариантов, если какой-то кусочек все-таки бросить Лисе, а потом ответить на вопрос пункта а)?

Решение.

Вороне Бог послал кусочки 5 разных видов.

а) Есть все кусочки по очереди - это значит выбирать только порядок их расположения, т. е. образовывать разные перестановки й3 5 элементов. Количество вариантов:

б) Делать бутерброды из двух кусочков - это значит выбирать разные пары из 5 данных кусочков; при этом порядок выбора не важен; количество вариантов:

в) Спрятать какие-то два кусочка -это значит выбрать пару из 5 данных кусочков без учета порядка, а остальные три съесть сразу; количество вариантов то же:

г) Если бросить Лисе кусочек, то останутся 4 кусочка, которые можно съесть одним из Р4 = 4! = 24 способов (меняется только по­рядок поедания). Но Лисе можно бросить любой из 5 имеющихся кусочков, при этом в каждом случае будут оставаться 4 разных на­бора кусочков, каждый из которых можно съесть 24 способами. По­этому общее число вариантов по правилу умножения будет равно:

5-Р₄= 5-24= 120.

Ответ: а) 120; б) 10; в) 10; г) 120.

11. «Проказница Мартышка, Осел, Козел и косола­пый Мишка затеяли сыграть квартет». Сколькими способами они могут:

а) по одному сесть за выбранные четыре инструмента;

б) выбрать 5 инструментов из 12 данных;

в) по одному сесть за какие-то 4 из выбранных 5 инструментов из 12 данных?

г) выгнать одного, не имеющего слуха, и потом сыграть на ка­ких-то 3 из выбранных 5 инструментов из 12 данных?

Решение.

а) Четыре «музыканта» могут сесть за 4 выбранные инструмента Р₄ =4!= 24 различными способами (меняется только порядок расположения«музыкантов»; это перестановки).

б) Выбрать 5 инструментов из 12 данных без учета порядка выбора можно

= 792 разными способами.

в) Выбрать 4 инструмента из 5 можно C = С = 5 различными способами; после этого рассесться за 4 инструментами можно Р₄ =4! = 24 различными способами общее число вариантов по правилу произведения равно

г) Выгнать одного из четырех музыкантов можно одним из С =4 разных способов; после этого выбрать какие-то 3 из вы­бранных пяти инструментов можно С = =10 разными способами. Далее в условии задачи не говорится о том, что остав­шиеся 3 музыканта будут рассаживаться за выбранными 3 инстру­ментами; они «сыграют на каких-то трех из выбранных 5 инстру­ментов», видимо, каким-то одним, произвольным способом разо­брав инструменты. При таком толковании условия задачи общее число способов по правилу произведения будет равно: С С =410 = 40.

Ответ: а) 24; б) 792; в) 120; г) 40.

12. В чемпионате России по футболу в высшей ли­ге участвуют 16 команд. Перед началом чемпионата газета «Спорт» провела Интернет-опрос читателей, задав им два вопроса: 1) какая команда получит золотые, какая - серебряные и какая - бронзовые медали? 2) какие две команды окажутся среди неудачников, т. е. займут два последних места? Читатели в своих ответах указали все возможные варианты и при ответе на первый, и при ответе на вто­рой вопросы.

а) Сколько вариантов состава неудачников указали участники опроса?

б) Сколько из них тех, в которые входит команда «Динамо»?

в) Сколько вариантов тройки призеров указали участники оп­роса?

г) Сколько из них тех, в которые входят «Спартак» и «Зенит»-

Решение.

а) Выбрать двух неудачников из 16 команд (без учета порядка выбора) можно С = 120 различными способами.

б) Если мы будем считать одним из неудачников команду «Ди­намо», т. е. фиксируем один элемент, то вторую команду - неудачника можно выбрать из 15 остальных команд С = 15 разными способами. Таким образом, среди 120 вариантов выбора двух не­ удачников в 15 вариантов входит команда «Динамо».

в) При выборе тройки призеров по условию задачи должен учи­тываться порядок выбора, поэтому общее количество вариантов равно = 3 360.

г) Если «Спартак» и «Зенит» входят в тройку призеров, то «Спартак» может занять любое из трех мест (3 варианта выбора), после этого «Зенит» может занять любое из двух оставшихся мест (2 варианта выбора), а на одно остающееся место можно выбрать еще одного призера из остальных 14 команд, т. е .14вариантоввы­бора. По правилу произведения общее число вариантов с участием «Спартака» и «Зенита» равно 3 • 2 14 = 84.

Ответ: а) 120; б) 15; в) 3 360; г) 84.

13. Из 20 вопросов к экзамену Вова 12 вопросов выучил, 5 совсем не смотрел, а в остальных что-то знает, а что-то нет. На экзамене в билете будет три вопроса.

а) Сколько существует вариантов билетов?

б) Сколько из них тех, в которых Вова знает все вопросы?

в) Сколько из них тех, в которых есть вопросы всех трех типов?

г) Сколько из них тех, в которых Вова выучил большинство вопросов?

Решение.

а) Для составления билета выбираются 3 вопроса из 20 имею­щихся, при этом порядок выбора значения не имеет. Общее число вариантов билетов равно:

б) Вова выучил 12 вопросов; из этих вопросов можно составить

разных билетов.

в) Количество билетов, в которых есть вопросы всех трех ти­пов, равно: 12 вариантов выбора вопроса, который выучил, умно­жить на 5 вариантов выбора вопроса, который совсем не смотрел, и умножить на 20 - 12 - 5 = 3 варианта выбора вопроса, в котором кое-что знает, всего = 180 разных билетов.

г) Билеты, в которых Вова выучил большинство вопросов, это билеты, в которых он знает два или все три вопроса. Билетов, в ко­торых Вова выучил все 3 вопроса - 220 (см. пункт б). Найдем, сколько есть билетов, в которых Вова выучил 2 вопроса: выбрать 2 вопроса из 12 изученных можно Cf2 разными способами; третий вопрос можно выбрать из 8 остальных вопросов (8 вариантов вы­бора). По правилу произведения количество билетов, в которых Вова выучил два вопроса, равно

Таким образом, количество билетов, в которых Вова выучил большинство вопросов, по комбинаторному правилу сложения равно 220+ 528=728.

Ответ: а)1140; б)220; в)180; г)748.