Руководство по решению дискретки

в) остался один случай, когда цифры, кратные двум, занимают три первых места, а последнее место занимает цифра, кратная трём: 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 могут быть получены перестановкой цифр этого числа. Количество таких чисел находим по формуле числа перестановок с повторениями

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

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

Ответ: 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 человека. Сколько студентов не знают ни одного из этих трех иностран-

|Р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 вариантов выбора мишеней. Все-

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

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

Решение. Всего шаров 12. Из них 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. По правилу произведения вероятностей получаем:

роятность равна 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 напильника. Найти вероятность того, что среди них хотя бы два напильника будут круглыми.

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

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

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

= 441.

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

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

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

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

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

Ответ: 103/143.

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

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

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

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

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

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

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

120 945 1065 .

5456 5456

Ответ: 1065/5456.

14.ТЕОРИЯ ГРАФОВ

14.1.Матрица смежности неориентированного графа

Приводим основные понятия, необходимые для выполнения задания:

1)число рёбер, выходящих из вершины, называется степенью этой вершины;

2)вершина называется чётной, если из неё выходит чётное число рёбер. Если же из вершины выходит нечётное число рёбер, то такая вершина называется нечётной;

3)вершина называется висячей, если степень её равна единице;

4)граф называется полным, если в нём каждые две различные вершины соединены точно одним ребром;

5)дополнением графа G называется граф G , содержащий все вершины графа G, все рёбра

полного графа, которых нет в графе G, и не содержащий ни одного ребра из графа G;

6)две вершины простого графа называются смежными, если они соединены точно одним

ребром;

7)в матрице смежности номера колонок и строк обозначают вершины графа. На пересечении строк и колонок ставят числа, показывающие, сколько рёбер соединяют соответствующие вершины.

Как выполнять задание данного подраздела, поясним на примере матрицы, приведённой на рис. 1.

Задание состоит в следующем. Изобразить граф и ответить на контрольные вопросы:

а) укажите степени вершин 2 и 7; б) укажите вершины, степень которых равна 3;

в) сколько чётных вершин в графе? Укажите их номера; г) укажите висячие вершины; д) сколько рёбер содержит дополнение графа?

е) укажите вершины, смежные относительно вершины 4; ж) из заданного графа удалили вершину 7. Сколько в получившемся под-

графе рёбер?

В заданном графе 11 рёбер. Следовательно, дополнение графа содержит 17 рёбер. Ответ: 17; е) из вершины 4 выходит три ребра. Они ведут к вершинам 1, 7 и 5. Эти вершины являются

смежными по отношению к вершине 4. Ответ: 1, 5, 7 (номера вершин необходимо упорядочить по возрастанию);

ж) в заданном графе 11 рёбер. Из вершины 7 выходит 5 рёбер. Если из графа удалить вершину 7, то вместе с вершиной будут удалены и выходящие из неё рёбра. Следовательно, в получившемся подграфе останется 11 – 5 = 6 рёбер. Ответ: 6.

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

14.5. Нахождение всех простых цепей, соединяющих две вершины графа

Нахождение всех простых цепей, соединяющих две заданные вершины графа, проиллюстрируем на двух примерах.

Пример 1. Найти все простые цепи, соединяющие вершины 1 и 5 графа, заданного следующим множеством ребер:

G = {{1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {3,4}, {3,5}, {4,5}}.

Определить числа a, b, c и d, где a – число простых цепей, содержащих по два ребра, b – содержащих по три ребра, c – по четыре ребра, d – по пять рёбер.

Для решения задачи сначала построим граф (рис. 1).

На последнем этапе получено четыре простые цепи из искомых. Это самые длинные простые цепи. Они проходят через все вершины графа.

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

Таким образом, в графе (рис. 1) содержится 11 простых цепей, соединяющих вершины 1 и 5. Из них одна цепь состоит из одного ребра, две – из двух, четыре – из трёх, четыре – из четырёх и 0

– из пяти рёбер. Ответ: 2, 4, 4, 0 (т.е. a = 2, b = 4, c = 4, d = 0).

Пример 2. Найти все простые цепи, соединяющие вершины 1 и 6 графа, заданного следующим множеством рёбер:

G = {{1,2}, {1,4}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {3,6}, {4,5}, {5,6}}.

Определить числа a, b, c и d (см. первый пример).

Как и в предыдущем случае, сначала строим граф (рис. 2).

Здесь найдено четыре цепи (подчёркнуты). Переходим к четвёртому этапу:

Таким образом, всего в графе существует восемь простых цепей, соединяющих вершины 1 и 6: четыре цепи состоят из трёх рёбер и четыре – из пяти. Ответ: 0, 4, 0, 4.