115904 (Элективные курсы по математике в профильной школе), страница 7

Уроки 1, 2.

Простейшие комбинаторные задачи: правило умножения и дерево вариантов, перестановки

Цель: сформировать представление о таком разделе математики, как «Комбинаторика», сформировать умения по решению простейших задач комбинаторики.

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

Пример: Начальник написал 10 писем и поручил своему помощнику надписать 10 конвертов с нужными адресами. Тот так и сделал, но дальнейшее перепоручил секретарше. Она выполнила это ответственное задание формально, то есть разложила письма по конвертам, не обращая внимания на адреса. Какова вероятность того, что ни одно письмо не попало в нужный конверт?

Оказывается, что вероятность такой масштабной ошибки превышает 36%.

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

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

Так как речь идёт о комбинациях объектов – задачи называются комбинаторными, а область математики – комбинаторикой.

Её основателями считают Пьера Ферма и Блеза Паскаля. Эти французские учёные XVII века первыми нашли ключ к составлению количественной оценки вероятности события. Они использовали метод, который позже был назван комбинаторным анализом или комбинаторикой.

Знакомство с новым для вас понятием начнём с двух простых задач, одну из которых решаем вместе, а другую самостоятельно.

Пример 1. Сколько чётных двузначных чисел можно составить из цифр 0, 1, 2, 4, 5, 9.

Решение. Составим таблицу: слева от первого столбца поместим первые цифры искомых чисел, а выше первой строки – вторые цифры этих чисел. Так как в двузначном числе впереди может стоять любая цифра, кроме 0, то строки будут отмечены цифрами 1, 2, 4, 5, 9. Значит, в нашей таблице будет 5 строк. На втором месте в искомом числе должна стоять чётная цифра. Значит, столбцы будут отмечены цифрами 0, 2, 4. Всего в таблице будет 3 столбца.

Клетки таблицы заполнятся следующим образом: первая цифра числа равна метке строки, а вторая цифра – метке столбца, поэтому каждое из интересующих нас чисел попадёт в определённую клетку таблицы. По строкам и столбцам мы перечислим все возможные варианты, значит, искомых чисел будет столько же, сколько клеток в таблице, то есть 5*3=15.

Ответ: 15.

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

Поэтому подобные задачи называют комбинаторными.

Пример 2. На завтрак Илья может выбрать плюшку, бутерброд, пряник или кекс, а запить их он может кофе, соком или кефиром. Из скольких вариантов завтрака Илья может выбирать? (самостоятельно).

Решение. Соберём все варианты в такой таблице:

В ней 3 строки и 4 столбца, они образуют 12 клеток. Так как выбор еды и напитка происходит независимо, то в каждой клетке будет стоять один из возможных вариантов завтрака и, наоборот, любой вариант завтрака будет записан в одной из клеток. Значит, всего вариантов столько же, сколько клеток в таблице.

Ответ: 12.

Видно, что, хотя примеры 1 и 2 очень разные, их решения совершенно одинаковые. Основаны они на общем правиле умножения.

Задачи:

1. Сколько двузначных чисел можно составить из цифр 1, 3, 5, 7, 9?

2. Сколько среди них чисел, кратных 5?

3. Сколько среди них чисел, кратных 11?

4. Сколько среди них чисел, кратных 3?