Лекция 21 Элементы комбинаторики и теории вероятностей

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

Например, на некотором предприятии было замечено, что при од­них и тех же условиях в среднем 1,5 % изготовленных деталей оказы­ваются бракованными, т. е. не удовлетворяющими стандарту. Это означает, что в партии, к примеру, 1000 деталей, еще не подвергнутых проверке будет примерно, 15 непригодных. Разумеется, что число бракованных изделий в некоторых случаях может быть большим, в других – меньшим, однако в среднем это число будет близко к 15, и в большинстве партий из 1000 деталей оно также будет близко к 15.

Другой пример. При бросании игральной кости (так называется идеальный куб, на гранях которого указаны цифры от 1 до 6), каждое число от 1 до 6 может выпасть случайно. Если, к примеру, мы бросим игральную кость 30 раз, то не можем с уверенностью сказать, что число 4 (или другое число из имеющихся на гранях) выпадет ровно 5 раз. Но, произведя достаточно большое число бросаний (экспериментов), мы можем убедиться, что каждая из цифр от 1 до 6 выпадет примерно одинаковое число раз.

Разумеется, что таких примеров можно привести достаточно много.

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

Если массовая операция такова, что событие А (например, получе­ние не бракованных деталей), наблюдается в среднем k раз среди произ­веденных n единичных операций, то говорят, что вероятность (или частота) наступления данного события равна отношению — .

Задачи теории вероятностей заключаются в разработке мате­матических методов для исследования случайных явлений.

1. Принцип математической индукции

Рассмотрим пример. Складывая последовательно четные числа 2, 4, 6, 8,..., будем иметь

2 = 2;

2 + 4 = 6;

2 + 4 + 6=12;

2 + 4 + 6 + 8 = 20;

2 + 4 + 6 + 8 + 10 = 30;

2 + 4 + 6 + 8+10+12 = 42;

…………………………..

Глядя на полученные результаты, т. е. числа 2, 6, 12, 20, 30 и 42,..., мы замечаем, что каждое из них есть произведение двух последователь­ных чисел, меньшее из которых равно числу взятых слагаемых: 2 = 1-2; 6 = 2 • 3; 12 = 3 • 4; 20 = 4 • 5; 30 = 5 • 6; 42 = 6 • 7,...

Возникает вопрос, справедливо ли это свойство при любом числе слагаемых, т. е. имеет ли место следующее утверждение:

для любого натурального числа п справедливо равенство

S (2n) = 2 + 4 + 6 + … + 2n = n (n + 1), (1)

где S(2k) — сумма первых 2к последовательных четных натуральных чисел.

Интуитивные соображения навели нас на мысль о том, что, воз­можно, существует какой-то определенный общий закон. Разумеется, справедливость этого закона не следует из частных заключений даже при условии, что он оказался верным для очень большого числа прове­рок. Несколько позже мы докажем, что, в действительности, замеченная нами закономерность справедлива для любого натурального числа n.

Рассмотрим еще один пример, связанный с именем крупнейшего российского математика швейцарского происхождения Л. Эйлера (1707-1783). Пусть имеется квадратный трехчлен:

(nN).

Подставляя в Р(n) вместо n последовательно натуральные числа 1, 2, 3, 4, 5, 6, соответственно, получим: Р(1) = 43, Р(2) = 47, Р(3) = 53, Р(4) = 61, Р(5) = 71, Р(6) = 83, Р(7) = 97. Легко заметить, что все полу­ченные числа являются простыми. Здесь, так же как и в первом приме­ре, напрашивается формулировка закона: при любом натуральном n величина Р(n) представляет собой простое число. Если в Р(n) вместо n мы подставим значения, например, n = 8, 9, 10, то, соответственно, по­лучим: P(8) = 113, Р(9) = 131, Р(10) = 151 — также простые числа. Од­нако уже при n = 41 получаем Р(41) = 412 + 41 + 41 = 41*43 — число составное. Таким образом, в этом случае предположение оказалось не­верным.

Из рассмотренных примеров мы можем заключить, что лишь в не­которых случаях частные примеры могут привести к установлению ка­кой-то общей закономерности.

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

Примером дедуктивного метода рассуждения является следующий: «из того, что сумма углов любого треугольника равна 180°, следует, что сумма углов равностороннего треугольника равна 180°».

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

В первом примере мы предположили, что при любом натуральном n имеет место равенство (1). Допустим, что мы проверили это равен­ство для всех натуральных чисел n от 1 до какого-то числа к, т. е. непо­средственно убедились, что равенство

S(2k) = 2 + 4 + 8 + … + 2n = n (n + 1) (2)

справедливо для чисел n < k. Для следующего числа k + 1 левая часть равенства (2) запишется в виде:

S(2(k + 1)) = 2 + 4 + 6 + 8 +… + 2k + 2 (k + 1). (3)

При условии (15.2) это выражение примет вид:

S (2(k+1)) = k (k+1) + 2(k+1),

откуда

S (2(k+1)) = (k+1) (k+2),

Таким образом,

S(2(k + 1)) = 2 + 4 + 6 + 8 + … + 2k + 2 (k + 1) = (k +1) (k+2),

а это равенство означает, что наше предположение справедливо и для следующего за k натурального числа k + 1.

Итак, непосредственно убедившись, что наше утверждение верно для некоторого натурального к, мы доказали, что оно верно и для сле­дующего натурального числа k + 1. Однако мы могли бы несколько уп­ростить наши рассуждения. Допустим, что мы проверили выполнимость предполагаемой закономерности при k = 1, и из допущения о том, что эта закономерность верна для некоторого натурального числа k, доказа­ли, что она верна и для следующего за к натурального числа k + 1. Тогда мы можем заключить, что наше предположение справедливо при всех k. В самом деле, при k = 1 мы непосредственно убедились в справедливо­сти нашего предположения и доказали, что оно верно при k = 2. Но, если оно верно для k = 2, то оно верно и для следующего числа k + 1, т. е. для числа 3 и т. д. для любого натурального числа.

Таким образом, равенство (1) справедливо для любого k е N.

Установленный нами метод называется методом полной матема­тической индукции или принципом математической индукции.

Форму­лируется он следующим образом:

Если некоторое предложение А(n) (n е N) справедливо для n = 1 и из предположения о том, что оно справедливо для n = k (где k — любое натуральное число), следует, что оно истинно и для следующего числа n = k +1, то предложение А (n) верно для любого n е N.

Из этой формулировки следует, что, если мы хотим доказать какое-то предложение методом математической индукции, то это доказатель­ство должно состоять из двух частей:

1. Мы должны непосредственно доказать, что наше предложение верно при n = 1.

2. Исходя из предположения, что предложение справедливо для ка­кого-то натурального k, надо доказать, что оно справедливо и для числа k +1.

На практике мы можем встретиться и с такими случаями, когда:

1. предложение А(n) при некоторых натуральных значениях невер­но, но, начиная с некоторого натурального значения n = m, оно имеет место для всех n > m;

2. предложение А (n) верно, начиная с n = 0;

3. предложение А (n) верно и для множества всех целых чисел, ли­бо для всех целых, начиная с некоторого числа.

Во всех этих случаях принцип математической индукции называет­ся обобщенным принципом математической индукции.

Пример 1. Найти все натуральные значения n, для которых справед­ливо неравенство 3ⁿ > n³.

Решение. При n = 1 имеем: 3 > 1³ = 1;

при n = 2: 9 > 8;

при n = 3: 27 = 27;

при n = 4: 81 > 64;

при n = 5: 243 > 125.

Отсюда можно предположить, что неравенство 3ⁿ > n³ справедливо для всех натуральных n, кроме n = 3. Докажем это предложение.

1. При n = 4 неравенство выполняется.

2. Допустим, что оно справедливо для некоторого k>3: т. е., что имеет место неравенство 3ⁿ > n³, и докажем, что Зk + x > (k + 1)³. Так как при натуральном k>3 справедливы неравенства k²>1 и (k-3)>1, то спра­ведливо и неравенство k²(k-3) > 1, откуда

k³ > 3k² + 1. (4)

Но при k > 3 справедливо и неравенство k (k² - 3) > 0 или

k³>3k (5)

Имеем З^k+1 = 3-3^k = 3^k + 3^k + 3^k.

Применим предположение индукции 3^k> k³, а затем заменим в преды­дущем равенстве второе и третье слагаемые правой части, согласно неравен­ствам (4) и (5), соответственно выражениями Зk² + 1 и Зk, и получим:

3^k+1 > k³ + 3k² + 1+3k = (k+1)³

Таким образом, неравенство 3ⁿ > n³ справедливо и для n = k + 1. Следовательно, оно верно и для любого натурального числа n, отлично­го от числа 3.