Элементы комбинаторики
Раздел математики, которым зачастую в школе «пренебрегают», является одним из наиболее интересных и сложных ее разделов — комбинаторика. Этот раздел математики учит учащихся рассуждать, перебирая различные варианты решения задачи, учит мыслить нестандартно, повышает их заинтересованность в изучении математики, развивает воображение и смекалку, что является одной из основных целей обучения. Ниже приведен план первого занятия (2 академических часа) в 7-м классе, позволяющий познакомить учащихся с основами комбинаторики.
Цель урока:
• познакомить учащихся с новым разделом математики — «Комбинаторика», с ее основными понятиями и задачами, использованием в практических целях;
• познакомить учащихся с основными приемами подсчета числа различных вариантов;
• показать учащимся основные методы решения комбинаторных задач и закрепить их при решении примеров.
Ход урока
Объяснение нового материала
В русских сказках повествуется, как, доехав до распутья, богатырь читает на камне: «Прямо поедешь — голову сложишь, направо поедешь — коня потеряешь, налево поедешь — меча лишишься». А дальше уже говорится, как он выходит из того положения, в которое попал в результате выбора. Но выбирать разные пути или варианты приходится и современному человеку. Эти пути и варианты складываются в разнообразные комбинации. И раздел математики, именуемый комбинаторикой, занят поисками ответов на вопросы: сколько комбинаций существует в том или ином случае, как из всех этих комбинаций выбрать наилучшую.
Люди, владеющие техникой решения комбинаторных задач, а следовательно, умеющие рассуждать, перебирать различные варианты решений, часто находят выход, казалось бы, из самой безвыходной ситуации. Примером мог бы послужить сказочный герой, барон Мюнхгаузен, который находил выход при любом условии.
Но и в жизни эти умения очень часто помогают человеку. Вот один случай умелого решения комбинаторной задачи.
Бесплатный обед. 10 молодых людей решили отпраздновать окончание института товарищеским обедом в ресторане. Когда все собрались, и первое блюдо было подано, заспорили о том, как усесться вокруг стола. Одни предлагали разместиться в алфавитном порядке, другие — по возрасту, третьи — по успеваемости, четвертые — по росту и т.д. Спор затянулся, суп успел остыть, а за стол никто не садился. Примирил всех официант, обратившийся к ним с такой речью:
— Друзья мои, оставьте ваши пререкания. Сядьте за стол как придется и выслушайте меня.
Все сели как попало. Официант продолжал:
— Пусть один из вас запишет, в каком порядке вы сейчас сидите. Завтра вы снова явитесь сюда пообедать, и разместитесь уже в ином порядке. Послезавтра сядете опять по-новому и т.д., пока не перепробуете все возможные размещения. Когда же придет черед вновь сесть так, как сидите вы здесь сегодня, тогда я начну ежедневно угощать вас бесплатно самыми изысканными обедами.
Предложение понравилось. Решено было ежедневно собираться в этом ресторане и перепробовать все способы размещения за столом, чтобы скорее начать пользоваться бесплатными обедами. Однако дождаться этого дня им не пришлось. И не потому, что официант не исполнил обещания, а потому, что число всех возможных размещений за столом чересчур велико. Оно равняется, — ни мало, ни много, — 3 628 800. Такое число дней составляет почти 10 тысяч лет! Это, на первый взгляд, невероятно, но так оно и есть!
Ну, а мы с вами сегодня рассмотрим некоторые задачи этого раздела математики, который, еще раз напомню, называется комбинаторикой. Мы познакомимся и научимся применять на практике несколько методов решения комбинаторных задач — задач, над решением которых мы задумываемся каждый день. Ведь в повседневной жизни нередко возникают проблемы, которые имеют несколько различных вариантов решения, и, чтобы сделать правильный выбор, важно не упустить ни один из них. Для этого надо осуществить перебор всех возможных вариантов или хотя бы подсчитать их число. Такого рода задачи называют комбинаторными.
Задачей комбинаторики можно считать задачу размещения объектов по специальным правилам и нахождения числа способов таких размещений.
Задача 1. Сколько двузначных чисел можно составить, используя цифры 1, 4 и 7?
Решение. Для того, чтобы не пропустить и не повторить ни одно из чисел, будем выписывать их в порядке возрастания. Сначала запишем числа, начинающиеся с цифры 1, затем с цифры 4, и наконец, с цифры 7. Получим следующую таблицу:
Таким образом, из трех данных цифр можно составить 9 различных двузначных чисел.
Вернемся к нашей задаче, построив для ее решения специальную схему.
Эта схема похожа на дерево, правда, «вверх ногами» и без ствола. Знак «*» изображает корень дерева, ветви дерева — различные варианты решения. Чтобы получить двузначное число, надо сначала выбрать первую его цифру, а для нее есть три варианта: 1, 4 или 7. Поэтому из «корня» проведены три «веточки» и на их концах поставлены цифры 1, 4 и 7.
Для выбора второй цифры также есть три варианта: 1, 4 или 7. Поэтому от каждой первой цифры проведено по три отрезка, на концах которых снова записано 1, 4 или 7. Итак, получено всего 9 различных двузначных чисел. Других двузначных чисел из этих трех цифр составить невозможно.
В последствии мы рассмотрим, как построение такого дерева возможных вариантов помогает решать самые разнообразные комбинаторные задачи.
Дополнительная подзадача. Сколько двузначных чисел можно составить, используя цифры 1, 4 и 7, если цифры десятков и единиц не повторяются?
Задача 2. Сколько трехзначных чисел можно составить, используя цифры 3 и 5?
Решение. Построим дерево различных вариантов.
Задача 3. Туристическая фирма планирует посещение туристами в Италии трех городов: Венеции, Рима и Флоренции. Сколько существует вариантов такого маршрута?
Решение. Обозначим города их первыми буквами. Тогда каждому маршруту будет соответствовать тройка букв: В, Р и Ф, каждая из которых используется только один раз, например, ВФР или ФРВ.
Путешествие можно начинать в любом из трех городов. Если первой посетить Венецию, то затем можно поехать в Рим или во Флоренцию. Если вторым посетить Рим, то третьей будет Флоренция, если второй будет Флоренция, то третьим будет Рим. Это первые два варианта путешествия.
Таким образом, всего существует 6 вариантов путешествия.
Задача 4. При встрече 8 приятелей обменялись рукопожатиями. Сколько всего было сделано рукопожатий?
Решение. Дадим каждому из приятелей номер — цифры от 1 до 8. Тогда каждое рукопожатие можно закодировать двузначным числом. Например, 47 — это рукопожатие между приятелями с номерами 4 и 7.
Ясно, что среди кодов рукопожатий у нас не появится, например, 33 – это означало бы, что один из друзей пожал руку сам себе. Кроме того, такие коды, как, например, числа 68 и 86, означают одно и то же рукопожатие, а значит, учитывать надо только один из них.
Договоримся, что из чисел, кодирующих одно и то же рукопожатие, мы всегда будем учиты-
вать меньшее. Поэтому из чисел 68 и 86 надо выбрать 68.
Коды рукопожатий естественно выписывать в порядке возрастания. Для подсчета их удобно расположить треугольником.
Число кодов равно: 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28.
Таким образом, всего было сделано 28 рукопожатий.
Задача 5. Служитель зоопарка должен дать зайцу два разных овоща. Сколькими различными способами он может это сделать, если у него есть морковь, свекла и капуста?
Решение. Построим дерево различных вариантов.
В итоге получим 6 вариантов, если считать, что мы делаем различие между МС и СМ и другими аналогичными парами. Но если учесть, что три из них эквивалентны трем другим парам (МС – СМ, МК – КМ, СК – КС), то имеем различных вариантов только три.
Задача 6. В спортивном лагере «Орленок» собирались проводить первенство по футболу. Незадолго до начала соревнований к начальнику лагеря пришел вожатый, который должен был судить встречи, и сказал:
— У нас на складе есть трусы и майки только трех цветов: белого, черного и синего. А команд у нас восемь. Как быть?
— Да совсем просто, Леня! — ответил тот. — Ведь необязательно, чтобы майки и трусы были одного цвета. Можно одну команду одеть в синие майки и белые трусы, а другую — в белые майки и синие трусы. Вот игроки и увидят, где свой, а где соперник.
— А хватит ли таких комбинаций на восемь команд?
— Не только хватит, еще одна останется про запас.
Решение. Посмотрим на запись:
Здесь первая буква показывает цвет майки, а вторая — цвет трусов. Можно видеть, что получилось девять различных комбинаций, так что все в порядке.
Составляя такие таблицы, можно найти число комбинаций и в случае, когда, например, есть майки пяти различных цветов, а трусы — четырех цветов. В этом случае в таблице будет пять строк и четыре столбца, а потому общее число комбинаций окажется равным 4∙5, то есть 20. Вообще, если имеются майки т различных цветов и трусы п различных цветов, то общее число комбинаций для составления формы играющих команд равно тжп.
Полученный результат верен и тогда, когда комбинируются не майки с трусами, а, например, ложки с вилками. Правило гласит:
Если надо выбрать пару вещей, причем первую вещь можно выбрать m способами, а вторую n способами, то пару можно выбрать mжn способами.
Бывает, что надо выбрать не две, а три или четыре вещи. Тогда число комбинаций ищут похожим образом: смотрят, сколькими способами можно выбрать каждую вещь, и перемножают полученные числа. Поэтому правило, приведенное выше, называют правилом произведения (или правилом умножения).
Вернемся к задаче о выборе формы для футболистов. Чтобы решить ее, была составлена таблица из трех строк и трех столбцов. Но если бы надо было еще выбирать цвет бутс, то пришлось бы составлять не одну, а несколько таблиц — по одной для каждого цвета бутс. Поэтому в этом случае удобнее воспользоваться помощью дерева возможных вариантов.
Такие деревья мысленно представляют себе шахматисты, выбирая наилучший ход в трудной позиции. Каждая полоса соответствует полуходу (ходу за белых или за черных). И думает шахматист: если я пойду так, а противник ответит так, а потом я пойду так, а он ответит так, то какой же ход мне выбрать? Мы уже видели, что с увеличением числа полос количество возможностей очень быстро возрастает. Поэтому пройти по всем веточкам дерева расчета бывает очень трудно, а иногда даже невозможно.
Со всем этим столкнулись ученые, составлявшие шахматные программы для вычислительных машин. Им удалось справиться со всеми трудностями, и теперь уже некоторые вычислительные машины играют сильнее мастера.
Задача 7. В том же спортивном лагере повар умел готовить четыре различных супа: щи, борщ, молочный суп и фасолевый суп. Из мясных блюд он умел стряпать котлеты, зразы, шницели, биточки и суфле. При этом к каждому мясному блюду он мог подать три гарнира: гречневую кашу, макароны и картофельное пюре. А на сладкое он делал тоже три блюда: компот, кисель или печеные яблоки. Сколько различных обедов умел готовить этот повар?
Решение. Если вы разобрались в правиле произведения, то ответ найдете сразу: повар умел готовить 4∙5∙3∙3, то есть 180 различных обедов. Так что он мог ни разу не повторить меню обеда за три смены.
Задача 8. В одном городе были трехзначные велосипедные номера. Но велосипедисты попросили, чтобы в этих номерах не встречались цифры 0 и 8, потому что первая из них похожа на вытянутое колесо, ну, а что значит для велосипедиста восьмерка колеса, знает каждый. Хватит ли им номеров, если в этом городе велосипеды имеют 710 человек?
Решение. Будем составлять номера следующим образом. Сначала выберем цифру сотен. Так как цифры 0 и 8 запретны, то остается 8 различных возможностей, а именно: 1, 2, 3, 4, 5, 6, 7, 9. Столько же возможностей и для выбора цифры десятков, и для выбора цифры единиц. А тогда по правилу произведения получаем, что общее число велосипедных номеров, которые можно было выдать в этом городе, равно 8∙8∙8, то есть 512. Так что на всех обладателей велосипедов номеров не хватило. Поэтому пришлось велосипедистам смягчить свои пожелания. Они согласились на цифру 0. После этого число номеров стало равно 9∙9∙9, то есть 729, и их хватило на всех.
Задача 9. Ребята Андрей, Боря, Витя, Гриша, Дима и Женя решили покататься на карусели. На ней было 6 сидений. Одно изображало льва, другое — тигра, третье — слона, четвертое — оленя, пятое — медведя, шестое — жирафа. Ребята заспорили, кому на какого зверя садиться. Поэтому они решили перепробовать все способы. Сколько раз пришлось им прокатиться на карусели?
Решение. Будем сажать ребят в алфавитном порядке их имен. Андрей может сесть на любого из шести зверей. Но когда он занял свое место, Боре осталось лишь 5 вариантов — одно место уже занято. Точно так же Вите досталось 4 варианта выбора, Грише — 3, Диме — 2, а когда садился на карусель Женя, ему оставалось только одно свободное место.
По правилу произведения находим, сколькими способами могли сесть на карусель ребята: 6∙5∙4∙3∙2∙1. В математике такое произведение обозначают 6! и называют 6-факториал. Перемножая эти числа, получим 720. Так что если бы даже они катались в день по 20 раз, то им пришлось бы больше месяца ходить каждый день в парк.
При условии, что ребят и мест на карусели было не 6, а 8, пришлось бы перемножать числа от 1 до 8. Это произведение равно уже 40 320.
А для десятиместной карусели и десяти ребят получается более 3 миллионов вариантов.
В другой раз на ту же карусель пришли только четверо ребят: Андрей, Боря, Витя и Гриша. Узнаем, сколькими способами могут они сесть на нее. По правилу произведения надо перемножить лишь четыре числа: 6, 5, 4 и 3. Получится 360.
А если бы трое ребят решили перебрать все способы катания на десятиместной карусели, то умножать пришлось бы только три числа: 10, 9 и 8.
Задача 10. Хоккейная комбинация. На поле 5 игроков. Начал комбинацию игрок № 1, продолжили игроки с другими номерами, а забил гол игрок № 5. Каждый хоккеист ударил по шайбе только один раз. На рисунке с помощью стрелок изображен один из возможных вариантов передачи шайбы между игроками в данной комбинации. Изобразите в тетради все другие возможные варианты передачи шайбы.
Закрепление нового материала
Каждый ученик получает «Рабочую карточку» с условиями задач, которые он начинает решать, работая в паре или в группе. Через некоторое время обсуждается решения первых задач. Домашнее задание из рабочей карточки дается с учетом выполненных заданий.
Рабочая карточка
1. Андрей зашел в магазин, чтобы купить майки. В магазине оказались майки четырех цветов: белые, голубые, красные, черные.
а) Сколько вариантов покупки есть у Андрея, если он хочет купить две майки? Подсказка. Обозначьте цвета маек буквами Б, Г, К, Ч. Запишите все возможные варианты покупки, осуществляя их перебор в алфавитном порядке.
б) Сколько вариантов покупки есть у Андрея, если он хочет купить две майки разного цвета?
2. В турнире по настольному теннису участвовали 5 человек.
а) Сколько было сыграно партий, если каждый участник сыграл с каждым по одной партии? Подсказка. Ответьте на вопрос, используя способ кодирования. Обозначьте участников турнира цифрами 1, 2, ...
3. В 6-м классе изучается 8 предметов. Сколько различных вариантов расписания можно составить на понедельник, если в этот день должно быть 5 уроков и все разные? Подсказка. На первом уроке можно провести любой из 8 предметов, на втором уроке – любой из оставшихся 7 предметов, на третьем уроке...
4. В магазине имеется четыре типа диванных подушек: круглые, овальные, прямоугольные и треугольные. Сколько вариантов покупки имеется у покупателя, который хочет приобрести две подушки? Подсказка. Решите задачу, построив дерево возможных вариантов.
5. Выпишите все трехзначные числа, используя при записи каждого числа цифры 1, 2, 3, причем каждую из них только один раз.
6. В классе три человека хорошо поют, двое других играют на гитаре, а еще один умеет показывать фокусы. Сколькими способами можно составить концертную бригаду из певца, гитариста и фокусника?
7. Имеется 3 вида конвертов и 4 вида марок. Сколько существует вариантов выбора конверта с маркой?
8. В буфете есть четыре сорта пирожков. Сколькими способами ученик может себе купить два пирожка? два разных пирожка?
9. Сколько существует шестизначных чисел, у которых:
а) третья цифра — 3;
б) последняя цифра — четная;
в) на нечетных местах стоят нечетные цифры;
г) на нечетных местах стоят четные цифры?
10. Фирма владеет четырьмя магазинами. Кассир магазина № 1 должен объехать остальные магазины, чтобы собрать выручку, и вернуться обратно. Какой из возможных маршрутов самый короткий?
11. Четыре друга купили билеты на один и тот же поезд. При этом оказалось, что два билета в один вагон, а два в другой. Из скольких вариантов посадки в два вагона им придется выбирать?
12. В четверг в первом классе должно быть три урока: русский язык, математика и физкультура. Сколько различных вариантов расписания можно составить на этот день?
13. В палатке имеется три вида мороженого: рожок, брикет и эскимо. Наташа и Данила решили купить по одной порции. Сколько существует вариантов такой покупки?
14. Проводится олимпиада по биологии. Для подарков участникам приготовили различные растения: кактусы, фикусы, лимоны, герани. Сколько различных призов можно из них составить, если каждому победителю решено давать по два любых растения? Как изменится решение задачи, если призы можно составлять только из двух разных растений?
15. Запишите все трехзначные числа, которые можно составить из цифр 2, 5, 9, используя при записи числа каждую цифру только один раз. Сколько всего таких чисел можно составить?
16. Наташа сшила кукле десять разных платьев, а Даша сшила своему мишке трое штанишек и четыре футболки. Как вы думаете, у кого больше разных нарядов – у куклы или у мишки?
17. Для начинки пирогов у Наташи есть капуста, яйца, зелень, лук и клубничное варенье. Сколько различных начинок можно приготовить из этих продуктов? При этом не надо забывать, что пироги должны быть вкусными. Вряд ли кто из вас захочет съесть пирог с начинкой из капусты с клубничным вареньем.
18. Наташа, Данила, Андрей и Маша — лучшие литераторы в классе. На школьную олимпиаду «Знатоки литературы» нужно выставить команду из двух человек. Можно ли составить 5 различных команд? Сколько различных команд, составленных из одной девочки и одного мальчика, может выставить данный класс?
19. В клетке сидит 7 мартышек. Служитель зоопарка должен дать каждой из них по два любых плода. При этом надо учесть, что капризные мартышки не любят получать одинаковые наборы. Сможет служитель угостить всех мартышек, если у него есть только бананы, яблоки и персики? Сколько еще других сортов фруктов надо иметь служителю, чтобы угостить всех мартышек?
20. В студии современного танца лучше всех танцуют четыре девочки — Аня, Ира, Оля и Яна и три мальчика – Боря, Володя и Гриша. Руководитель студии должен отправить на конкурс одну танцевальную пару, составленную из мальчика и девочки. Из скольких вариантов он должен выбирать?
21. Данила идет на день рождения к Наташе и хочет подарить два букета — один Наташе, другой ее маме. Сколькими способами он может выбрать два букета, если в магазине есть букеты гвоздик, тюльпанов и сирени?
6. Фирма владеет четырьмя магазинами. Кассир магазина № 1 должен объехать остальные магазины, чтобы собрать выручку, и вернуться обратно. Какой из возможных маршрутов самый короткий?
Литература
1. Математика. 5 класс/ Под ред. Г.В. Дорофеева, И.Ф. Шарыгина. — М.: Просвещение, 2007.
1. Математика. 6 класс/ Под ред. Г.В. Дорофеева, И.Ф. Шарыгина. — М.: Просвещение, 2007.
2. Виленкин Н.Я. Популярная комбинаторика. — М.: Наука, 1975.