Повторение ранее изученного материала (11 мин).

Рассмотрим следующую задачу:

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

Решение: Мы можем записывать наше решение следующим образом : «1 вариант: первая полоса – красная, вторая – синяя, третья – белая.» и т.д. Но это очень долго и не удобно, записывая так, сложно сориентироваться все ли варианты мы записали, и не повторились ли мы где-нибудь. Поэтому очень удобно ввести кодирование, т.е. некоторое условное обозначение перебираемых в задаче объектов. В нашем случае мы заменим первой буквой каждый цвет полосы. Белый соответственно – «Б», красный – «К» и синий – «С».  

Введя кодирование, запись решения задачи очень упрощается. Мы имеем множество из трех элементов {Б, К, С}. Нужно составить различные комбинации из трех элементов, при этом порядок элементов учитывается. Например, запись «БКС» будет обозначать, что первая полоса флага – белая, вторая – красная, третья – синяя. Подобные задачи мы уже решали методом непосредственного перебора и построением дерева возможных вариантов. 

Задача 2. При встрече 8 приятелей обменялись рукопожатиями. Сколько всего было сделано рукопожатий?

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

Каждому приятелю даем номер от 1 до 8, а рукопожатия закодируем следующим образом: например число 24 означает что 2-ой приятель пожал руку 4-му. При чем число 35 и 53 означают одно и тоже рукопожатие, и брать будем меньшее из них. Коды рукопожатий мы можем оформить следующей таблицей:

12, 13, 14, 15, 16, 17, 18,

23, 24, 25, 26, 27, 28,

34, 35, 36, 37, 38,

45, 46, 47, 48,

56, 57, 58,

67, 68,

78.

Таким образом, у нас получилось 1+2+3+4+5+6+7=28 рукопожатий.

 3. Выполнение задания (30 мин).

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

Задача 1. Группа туристов планирует осуществить поход по маршруту Антоново – Борисово – Власово – Грибово. Из Антоново в Борисово можно сплавиться по реке или дойти пешком. Из Борисово во Власово можно пройти пешком или доехать на велосипедах. Из Власово в Грибово можно доплыть по реке, доехать на велосипедах или пройти пешком. Сколько всего вариантов похода могут выбрать туристы? Сколько вариантов похода могут выбрать туристы при условии, что хотя бы на одном из участков маршрута они должны использовать велосипеды?

Решение: Построим для этой задачи дерево возможных вариантов:

Пусть у нас «П»-обозначает путь пешком

«Р» - сплавиться по реке

«В» - доехать на велосипедах.

Ответ на второй вопрос также хорошо просматривается по дереву возможных вариантов.

Но эту задачу можно решить по-другому, с помощью рассуждений. Из Антоново в Борисово у нас 2 варианта каким образом продолжать путь, из Борисово во Власово тоже 2 варианта, т.е. на каждый вариант первого участка пути у нас есть по 2 варианта второго участка пути и того на данном этапе у нас будет 2*2=4 варианта выбора способа передвижения. На каждый из этих 4 вариантов существует по 3 варианта способа передвижения по третьему участку пути из Власово в Грибово, т.е. 4*3=12. Ответ в этой задаче мы получили умножением.

Такой способ подсчета называется правилом умножения, он возможен, если дерево возможных вариантов является «правильным»: из каждого узла выходит одно и тоже число веток на одном и том же ярусе.

Задача 2. От турбазы к горному озеру ведут 4 тропы. Сколькими способами туристы могут отправиться в поход к озеру, если они не хотят спускаться по той же тропе, по которой поднимались?

Решение : Занумеруем тропы числами от 1 до 4 и построим дерево возможных вариантов:

Чтоб подняться у нас есть 4 тропы (4 варианта) и на каждый из них есть по 3 оставшихся тропы (3 варианта), чтоб спуститься, т.е. 4*3=12 маршрутов подхода к озеру. А теперь представим, что к озеру ведут не 4, а 10 троп. Сколько в этом случае существует маршрутов, если по-прежнему решено спускаться не по той тропе, по которой поднимались. Изобразить дерево возможных вариантов в такой ситуации очень сложно. Гораздо легче решить эту задачу с помощью рассуждений. Подняться к озеру можно по любой из 10 троп, а спускаться по любой из оставшихся 9 троп. Таким образом, всего получим 10*9=90 различных маршрутов похода.

Обе эти задачи мы решили, используя правило умножения, которое звучит следующим образом: пусть необходимо выполнить к независимых действий, если первое действие мы можем выполнить п₁ способами, после чего второе действие можем выполнить п₂ способами и т.д. до k -го действия, которое можно выполнить п _k способами, тогда выполнить все k действия в указанном порядке можно п₁∙ п₂∙…∙ п _k способами. Обратить внимание, что, применяя правило умножения, мы учитываем порядок действий. То есть правило умножения применяется для подсчета упорядоченных наборов.

Рассмотрим две задачи:

Задача 3. Сколькими способами из класса, в котором учатся 30 школьников, можно выбрать капитана команды для математических соревнований и его заместителя?

Решение: На роль капитана может быть выбран любой из 30 учащихся, а его заместитель – любой из 29 оставшихся учеников. Таким образом, получаем 30∙29 = 870 способов.

Задача 4. Сколькими способами из класса, в котором учатся 30 школьников, можно выбрать двоих для участия в математической олимпиаде?

Решение: Нам не важно, кто капитан, а кто заместитель, нам нужны всего лишь два участника, поэтому получаем, что у нас каждая пара учащихся в произведении повторяется два раза. Поэтому ответом для второй задачи будет (30∙29):2.

Еще одним способом подсчета комбинаторных наборов является использование правила суммы.

Задача 5. Из класса нужно выделить одного дежурного, мальчика или девочку. Сколько существует способов для выбора дежурного, если в классе 22 девочки и 18 мальчиков?

Решение: Выбрать одну девочку из 22 мы можем 22-мя способами, а одного мальчика из 18 можно 18-тью способами. Тогда выбрать одного дежурного мальчика или девочку можно (18+22) способами. Отсюда получаем, что существует 40 способов для выбора дежурного.

Для подсчета вариантов мы использовали здесь правило суммы, которое можно сформулировать так: если два действия взаимно исключают друг друга, причем одно из них можно выполнить п способами, а другое – m способами, то какое-либо одно из них можно выполнить n + m способами. В нашем примере действия исключают друг друга, так как мы должны выбрать либо мальчика из одного множества, либо девочку из другого.