Изучение основ комбинаторики и теории вероятностей (стр. 12 из 17)
Задача 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 различных маршрутов похода.
Обе эти задачи мы решили, используя правило умножения, которое звучит следующим образом: пусть необходимо выполнить к независимых действий, если первое действие мы можем выполнить п1 способами, после чего второе действие можем выполнить п2способами и т.д. до k-го действия, которое можно выполнить пkспособами, тогда выполнить все k действия в указанном порядке можно п1∙ п2∙…∙ п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 способами. В нашем примере действия исключают друг друга, так как мы должны выбрать либо мальчика из одного множества, либо девочку из другого.
4. Домашнее задание(2 мин).
1. Пароль состоит из двух букв, за которыми следуют 4 цифры или из 4 букв, за которыми следуют 2 цифры. Сколько можно составить разных паролей, если из 33 букв русского алфавита используются только буквы: а, б, в, г, д, е, ж, и, к, л, м, н, п, р, с, т и все десять цифр? А сколько можно получить разных паролей, если из множества букв исключить дополнительно буквы а, е и с, а к 10 цифрам добавить символ *? C:\www\doc2html\work\bestreferat-249029-13972164196688\сайт\web\3.1.html
5. Подведение итогов урока (1 мин).
Наступило время подвести итоги нашего урока. Сегодня мы с вами познакомились с правилом сложения и умножения, а также научились решать задачи с их помощью. Всем спасибо за работу. До свидания.
Урок № 3. Перестановки, размещения, сочетания.
Цели: познакомится с основными понятиями комбинаторики, научиться применять полученные знания для решения задач, а так же закрепить такие понятия, как правило сложения и правило умножения.
Тип урока: комбинированный.
Ход урока
1. Организационный момент и постановка цели урока (5 мин).
Сегодня мы с вами познакомимся с такими понятиями как, размещение, перестановка, сочетание, закрепим такие понятия, как правило суммы, правило умножения, познакомимся с формулами для вычислений и научимся их применять для решения задач. Для начала мы проверим домашнее задание.
2. Выполнение задания (35 мин).
Размещения.
Определение. Пусть имеется множество, содержащее n элементов. Каждое его упорядоченное подмножество, состоящее из k элементов, называется размещением из n элементов по k элементов.
Рассмотрим задачу .
Задача 1. Сколькими способами можно составить различные двузначные числа из четырех цифр 1,2,3,4 ?
Решение: В этой задаче речь идет о размещениях из четырех элементов по два.
1 способ. Перебор вариантов.
Рассмотрим все такие числа : 12 13 14 23 24 34
21 31 41 32 42 43
Всего таких чисел 12.
Правило суммы.
Если элемент a можно выбрать m способами, а элемент b – n способами, причем любой выбор элемента a отличен от любого выбора элемента b, то выбор “a или b” можно сделать m + n способами.
Правило произведения.
Если из некоторого множества А элемент ai можно выбрать КA способами, а элемент bj из множества В – КB способами, то совокупность (ai ; bj ) можно образовать КA* КB способами. Правило верно и для совокупностей, состоящих из большего, чем два числа элементов.
2 способ. С применением правила произведения.
Первая цифра числа выбирается 4 способами из данных цифр, а вторая цифра числа выбирается 3 способами (из оставшихся трех цифр). По правилу произведения 4 * 3=12 (способов).
Формула для вычисления числа размещений.
Первый элемент размещения выбирается n способами, второй элемент ( n -1) способами, …, k-ый элемент (n -(k -1)) способами ,т.е. можно ввести формулу для числа вариантов
= (n –1)·(n – 2) …·(n – (k – 1))или
= 
, где - число размещений из n по k ,( n! читается n - факториал); n!=1*2*3*….* n ; 0!= 1 по определению;
1!= 1.
3 способ. Применение формулы для вычисления числа размещений.
= 
= 
= 3 · 4 =12 .Задача 2. Набирая номер телефона, абонент забыл две последние цифры. Сколько различных вариантов нужно набрать, чтобы дозвониться, если абонент помнит, что цифры различны?