Примеры комбинаторных задач

Дата _______________класс

Урок № 72

Тема урока: «Примеры комбинаторных задач»

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

Задачи:

- познакомить обучающихся с понятием «комбинаторика», комбинаторные задачи, способами решения комбинаторных задач;

- формировать навыки применения комбинаторных задач при решении простейших упражнений;

- развивать математическое мышление и логику;

- развивать самоконтроль и взаимоконтроль, опыт общения при работе в парах;

- воспитывать навыки коммутативности в работе, умение слушать другого, уважение к мнению товарища;

- воспитывать у обучающихся такие нравственные качества, как настойчивость, аккуратность, инициативность, точность, самостоятельность, активность.

Планируемые результаты:

Личностные: формирование коммуникативной компетентности в общении со сверстниками, умение ясно, четко излагать свои мысли в устной и письменной речи.

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

Регулятивные: самостоятельно формулируют познавательную цель и строят свои действия в соответствие с ней, умеют анализировать, делать выводы: рефлексия способов и условий действия, контроль и оценка процесса и результатов деятельности.

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

Тип урока: урок «открытия новых знаний».

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

Ход урока

1. Организационный момент

Здравствуйте ребята. Я надеюсь, что наше общение сегодня будет плодотворным и полезным, как для вас так и для меня. Обговорим правила, которые будут действовать на уроке:

• если хотим ответить, поднимаем руку,

• на уроке будет действовать правило "правой руки", если учитель поднимает правую руку, то все замолкают и смотрят на учителя.

2. Активизация познавательной деятельности и сообщение темы урока:

Решить старинную задачу VIII века:

Волк, коза и капуста

Некий человек должен был перевезти в лодке через реку волка, козу и капусту. В лодке мог поместиться только один человек, а с ним или волк, или коза, или капуста. Но если оставить волка с козой без человека, то волк съест козу, если оставить козу с капустой, то коза съест капусту, а в присутствии человека никто никого не ест. Как перевезти груз через реку?

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

3. Формирование новых понятий и способов действий.

Комбинаторика - раздел математики, посвящённый решению задач выбора и расположения элементов в соответствии с данными условиями.

Слово «комбинаторика» происходит от латинского слова combinare, которое означает «соединять, сочетать». Методы комбинаторики находят широкое применение в физике, химии, биологии, экономике, теории вероятностей и других областях знаний. Например, в химии (анализ возможных связей между химическими элементами), экономика (анализ вариантов купли-продажи акций), в азартных е играх (подсчёт частоты выигрышей), в криптографии (разработка методов шифрования), в доставке почты (рассмотрение вариантов пересылки), в военном деле (расположение подразделений)

Рассмотрим некоторые комбинаторные задачи и способы их решения

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

А) Задачи, решаемые перебором возможных вариантов:

Из группы теннисистов, в которую входят четыре человека – Антонов, Григорьев, Сергеев и Федоров, тренер выделяет двоих для участия в соревнованиях пар. Сколько существует вариантов выбора такой пары?

Решение: Составим сначала все пары, в которые входит Антонов (для краткости будем писать первые буквы фамилий). Получим три пары: АГ, АС, АФ.

Выпишем теперь пары, в которые входит Григорьев, но не входит Антонов. Таких пар две: ГС, ГФ.

Далее составим пары, в которые входит Сергеев, но не входят Антонов и Григорьев. Такая пара только одна: СФ. Других вариантов составления пар нет, так как все пары, в которые входит Федоров, уже составлены.

Итак, мы получили шесть пар: АГ, АС, АФ, ГС, ГФ, СФ.

Ответ: 6 вариантов.

Б) Задачи, решаемые при помощи построения дерева возможных вариантов:

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

№ 714 В кафе предлагают два первых блюда: борщ, рассольник – и четыре вторых блюда: гуляш, котлеты, сосиски, пельмени. Укажите все обеды из первого и второго блюд, которые может заказать посетитель. Проиллюстрируйте ответ, построив дерево возможных вариантов.

Решение: Обед состоит из первого и второго блюда:

Первые блюда: борщ и рассольник Б Р

Вторые блюда: гуляш, котлеты, сосиски, Г К С П Г К С П

пельмени. Итак, мы получили восемь возможных вариантов обедов: БГ, БК, БС, БП, РГ, РК, РС, РП,

Ответ: 8 вариантов.

Е) Задачи, решаемые при помощи комбинаторного правила умножения:

Пусть имеется n элементов и требуется выбрать из них один за другим k элементов. Если первый элемент можно выбрать способами, после чего второй элемент можно выбрать способами из оставшихся, затем третий элемент можно выбрать способами из оставшихся и т.д., то число способов, которыми могут быть выбраны все k элементов, равно произведению * * * … * .

№ 728 Петр решил пойти на новогодний карнавал в костюме мушкетера. В ателье проката ему предложили на выбор различные по фасону и цвету предметы: пять видов брюк, шесть камзолов, три шляпы, две пары сапог. Сколько различных карнавальных костюмов можно составить из этих предметов?

Решение: Петр может выбрать брюки пятью способами, камзолы – шестью способами, шляпы – тремя способами и сапоги – двумя. Итак, Петр может составить из этих предметов по комбинаторному правилу умножения 5×6×3×2 =180 различных карнавальных костюмов.

Ответ: 180 карнавальных костюмов.

4. Применение знаний, умений и навыков в различных ситуациях (стандартных и нестандартных):

№ 715 У Ирины пять подруг: Вера, Зоя, Марина, Полина и Светлана. Она решила двух из них пригласить в кино. Укажите все возможные варианты выбора подруг. Сколько таких вариантов?

1 способ Решение: Решим задачу перебором возможных вариантов. Составим сначала все пары, в которые входит Вера ( для краткости будем писать первые буквы имен девочек). Получим четыре пары: ВЗ, ВМ, ВП, ВС.

Выпишем теперь пары, в которые входит Зоя, но не входит Вера. Таких пар три: ЗМ, ЗП, ЗС.

Далее составим пары, в которые входит Марина, но не входят Вера и Зоя. Таких пар только две: МП, МС. Еще осталась пара ПС. Других вариантов составления пар нет.

Итак, мы получили десять пар: ВЗ, ВМ, ВП, ВС, ЗМ, ЗП, ЗС, МП, МС, ПС.

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

Ребра графа показывают связь в парах, таких ребер 10, значит, всего 10 вариантов выбора подруг.

Ответ: 10 вариантов.

№ 716.

В этой задаче при выборе пар входов порядок выбора имеет значение: АВ означает, что посетитель вошел через А, а вышел через В, а ВА означает, что вошел через В, а вышел через А.

Фиксируем каждый вход по очереди и дописываем к нему в пару оставшиеся:

А: АВ, АС, АD;

В: ВА, ВС, ВD;

С: СА, СВ, СD;

D: DA, DB, DC.

Итого – 12 вариантов.

№ 718 (а) Составьте все возможные двузначные числа из указанных цифр, используя в записи числа каждую из них не более одного раза: а) 1, 6, 8.

Решение: Построим дерево возможных вариантов:

Ответ: 16, 18, 61, 68, 81, 86.

№ 720. Используя цифры 0, 2, 4, 6, составьте все возможные трехзначные числа, в которых цифры не повторяются.

Решение: Можно построить дерево возможных вариантов. Необходимо помнить, что нуль не может быть первой цифрой в числе, в старший разряд можно поместить цифру 3 способами, в следующий – 3 способами ( включая нуль ), в последний – 2 способами ( из оставшихся двух) Используя комбинаторное правило умножения, получаем: 3 * 3* 2 = 18 чисел.

Ответ: 18 чисел.

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

Решение:

Дадим каждому из приятелей номер – от 1 до 8. Тогда каждое рукопожатие можно закодировать двузначным числом. Например, 47 – это рукопожатие между приятелями с номерами 4 и 7.

Ясно, что среди кодов рукопожатий у нас не появится, например, 33 – это означало бы, что один из друзей пожал руку сам себе. Кроме того, такие коды, как, например, числа 68 и 86, означают одно и то же рукопожатие, а значит, учитывать надо только одно из них.

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

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

Число кодов равно: 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28. Таким образом, всего было сделано 28 рукопожатий

Ответ: 28 рукопожатий.

5. Рефлексия.

Учитель:

- Что вы нового узнали сегодня на уроке?

-Что изучает комбинаторика?

-Какие способы решения комбинаторных задач вы знаете?

-Что такое дерево возможных вариантов?

-Когда применить при решении задач правило умножения?

-Как вы думаете, можете ли использовать этот материал в повседневной жизни? Если да, то в какой ситуации.

6. Домашнее задание: пункт 30 № 714, 719, 721.

6