Методы решения комбинаторных задач как средство обработки и интерпретации информации

Число, место и комбинация — взаимно перекрещивающиеся, но отличные сферы мышления, к которым можно отнести все математические идеи.

Дж. Сильвестр

В результате изучения главы 5 студент должен: знать

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

Понятие комбинаторной задачи

Очень часто в педагогике приходится решать конфликтные ситуации. С этим процессом неразрывно должна быть связана привычка рассматривать ситуацию с разных сторон. Как любая гуманитарная наука педагогика осмысливает разные точки зрения па педагогический феномен. Как эмпирическая наука во многом педагогика использует такой метод обоснования, как полная индукция, полный перебор всевозможных комбинаций изучаемых объектов. Полная индукция невозможна без уверенности в ее полноте, т. е. знания количества комбинаций, требующих рассмотрения, чтобы индукция была доказательной. Дифференцированный подход к обучению подразумевает разделение учащихся на большие и малые группы по разным признакам и подсчет возможного количества разных комбинаций учащихся в группах. Хороший учитель обязательно учитывает при конструировании педагогического процесса влияние множества факторов и их комбинаций на педагогический процесс. Это означает, что в педагогике востребован вопрос о количестве разных комбинаций имеющихся факторов, влияющих на исследуемый процесс. Решение подобных вопросов является предметом такого раздела математики, как комбинаторика.

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

Таким образом, основным объектом комбинаторики являются комбинации из элементов данного множества. В этом разделе математики они определяют взгляд на предлагаемую информацию. Цель обработки информации с точки зрения комбинаторики будет заключаться в выделении из имеющейся информации комбинаций, определении их количественных характеристик и подсчете их количества. С этой точки зрения надо будет научиться очищать информацию от всего неважного на данный момент. Поэтому важно разобраться прежде всего, что такое комбинации.

Комбинацией из элементов данного множества называется подмножество данного множества, имеющее заданное свойство.

Пример 5.1.

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

Решение

Комбинацией в данном сюжете является танцевальная пара. Ясно, что каждая танцевальная пара — это двухэлементное подмножество исходного множества, состоявшего из пяти человек. Заданными в сюжете свойствами подмножеств являются: а) количество элементов равно двум; б) разнополость. Поскольку в данном тексте описано исходное множество, его подмножества и заданы свойства подмножеств, то все три требования определения комбинаций присутствуют, и данный сюжет может стать объектом комбинаторики. Основными количественными характеристиками комбинаций данного сюжета являются количество элементов в исходном множестве и количество элементов в подмножестве.

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

Таким образом, чтобы ответить на вопрос о количестве пар с точки зрения комбинаторики, надо первой девушке предложить пообщаться с каждым из юношей — это будет уже три комбинации, а потом дать шанс и второй девушке, сопоставив ее с каждым из трех парней, — это еще три комбинации. В результате надо взять два раза, но три юноши, что соответствует действию умножение в математике. Итого — шесть комбинаций.

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

Правило произведения. Если некоторый объект А можно выбрать т способами, а после каждого такого выбора другой объект В можно выбрать k способами, то пары объектов А и В можно выбрать mk способами.

Самым существенным в этой формулировке является то, что если надо выбрать объекты А и В, то надо перемножить количества соответствующих способов выбора.

Действительно, каждому из т способов выбора элементов А надо сопоставить k способов выбора элементов В, т. е. т раз взять по k способов, что соответствует определению действия умножения.

Второе основное правило комбинаторики связано с союзом или. Изменим немного пример 5.1.

Пример 5.2.

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

Решение

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

Эта ситуация находит свое обобщение во втором правиле комбинаторики.

Правило суммы. Если некоторый объект А можно выбрать т способами, а объект В можно выбрать k способами (независимо от выбора Л), то объект «А или В» можно выбрать т + к способами.

Все очень естественно и просто. Но в математических формулировках каждое слово выверено, ни одно из них нельзя игнорировать. Так и здесь недаром присутствует выражение в скобках — независимый выбор объектов А или В. Например, если подарок надо составить из одного учебного пособия из пяти имеющихся пособий или одной книги из четырех имеющихся книг, то решение неоднозначно. Ведь среди книг вполне могут оказаться и учебные пособия, а среди учебных пособий могут быть как книги, так и, например, географические карты. Так что применять правило можно и нужно, но осторожно.

Если перефразировать два основных правила комбинаторики для пользователей, то слово «или» можно заменить на математическом языке знаком «+» и, соответственно, действием сложения, а слову «и» на математическом языке соответствуют знак «•» и действие умножения. В русско-математический словарик можно занести следующую информацию (табл. 5.1).

Таблица 5.1

Основные правила комбинаторики.

Полезным для многих оказывается мнемоническое правило, позволяющее прочно, но формально запомнить эту таблицу и, соответственно, основные правила комбинаторики и легко их актуализировать в стрессовой ситуации решения сложных задач. Сравним верхнюю и нижнюю строчки табл. 5.1. Можно заметить, что затраты на написание верхней строчки гораздо больше, чем на написание нижней строчки. Союз или писать дольше, чем союз и, а знак «плюс» чертить дольше, чем поставить точку.

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

• • этап 1: краткая словесная (вербальная) формулировка условия;
• • этап 2: полная запись условия на языке математических символов.

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

«Выбрать … (…) из … (…)».

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

Пример 5.3.

В читальном зале есть 12 учебников, но комбинаторике, среди которых четыре новых. Наудачу берем два учебника. Сколько вариантов получить новые учебники?

Следует интерпретировать требование задачи в следующем виде: «Выбрать два (новых) из четырех (новых)».

Очень часто возникают ошибки при решении этой задачи. Например, встречается решение, связанное с выбором двух новых учебников из 12 учебников, что неверно. Как и то, что молодой человек вряд ли будет выбирать себе подругу из числа всех однокурсников, так как среди них может попасться и мужчина.

На первом этапе возникают затруднения в интерпретации информации, если предлагаемый текст содержит несколько синонимических наименований или просто требует проникновения в ситуацию, представления себя внутри описываемой ситуации. Например, надо распределить три призовых места в каком-либо конкурсе среди десяти студентов. В данном случае бывает продуктивной переформулировка выбора трех мест из десяти студентов на выбор трех фамилий в список награжденных из десяти фамилий всех студентов, участвующих в конкурсе. Привычка задумываться об одинаковом наименовании элементов исходного множества и подмножества помогает в правильной формулировке сути выбора, описанного в комбинаторной задаче.

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

Например, у студентов часто вызывает затруднение осмысление ситуации составления расписания и распределения консультаций между преподавателями кафедры по одному и тому же предмету с условием проведения одной консультации каждый день и одним преподавателем один раз. Поставьте себя на роль диспетчера, представив, что реально должен сделать диспетчер, чтобы составить такое расписание. Осознав, что требуется записать в нужные строки расписания фамилии из списка фамилий преподавателей, студенты сами правильно формулируют краткое вербальное условие данной комбинаторной задачи: «Выбрать столько-то фамилий из стольких-то фамилий».

В реально поступающей к нам информации содержится много отвлекающих моментов. Следует научиться отбрасывать все несущественное по отношению к поставленным целям. Необязательно в тексте, предполагающем комбинаторную обработку, будут только необходимые данные, как это было в сюжетных задачах из школьных учебников. Кроме того, возможно, в обрабатываемом вами тексте будут не только присутствовать избыточные данные, но и отсутствовать необходимые сведения, которые придется добывать из своего субъектного опыта или дополнительной литературы. Например, некоторых студентов ставит в тупик следующая задача: «Сколькими способами можно сформировать стартовый состав волейбольной команды из класса, в котором учатся 25 школьников, умеющих играть в волейбол?» Чтобы обработать этот текст, надо вспомнить допустимое количество игроков на волейбольной площадке или покопаться в правилах волейбола. В результате краткое вербальное условие описываемой ситуации будет выглядеть следующим образом «Выбрать шесть фамилий из 25 фамилий».

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

«Выбрать … (…) из … (…) и (или) … (…) из … (…).».

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

Пример 5.4.

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

Решение

Подводный камень решения этой задачи связан с формализмом в применении правил. В условии есть слово «и», значит, решает формалист, выполняем действие умножения. При этом он забывает о великом и могучем русском языке, который использует широкую палитру оттенков и иносказаний типа «Хочешь чая? Да нет, наверное!», которые не всякий иностранец поймет. По это уже относится не к математике, а к здравому смыслу человека, обрабатывающего информацию. Правильная краткая формулировка условия задачи будет выглядеть так.

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

Ответ: 12 способов.

Первый этап решения комбинаторных задач прекрасно формирует и оттачивает важнейшее методическое умение разделения целого на части, сложного действия на простейшие операции, формулировки четких, конкретных элементарных указаний для выполнения какого-либо задания учителя. Например, часто встречаются ошибки при осмыслении следующей фразы: «Собрание из 100 человек выбирает председателя, секретаря и трех членов редакционной комиссии». Решающий должен представить себе последовательность изменяющихся ситуаций и дать четкие указания ведущему собрание. Полезно задать себе вопрос: «Что сделает председатель после того, как его выберут?» По-видимому, сядет в президиум, и только после этого начнутся выборы следующих участников действа. А это значит, что количество человек в зале изменится.

Решение в этом случае может выглядеть гак:

Этап 1. Краткая словесная (вербальная) формулировка условия:

«Выбрать 1 (чел.) из 100 (чел.), и 1 (чел.) из 99 (чел.), и 3 (чел.) из 98 (чел.)».

Этап 2. Полная запись условия на языке математических символов: 100*99- (число способов выбора 3 из 98).

Подсчитать количество способов выбрать несколько элементов из данного множества, т. е. подмножества из множества, сложнее. Для этого надо уметь использовать дополнительно основные формулы комбинаторики, которые рассмотрим в следующем параграфе. Но прежде чем использовать математические формулы, стоит потратить время на обработку предъявленной информации, переосмысление условия задачи и не пренебрегать первоначальной краткой вербальной переформулировкой комбинаторных задач через слова «выбрать», «и (или)» и одинаковые наименования объектов выбора.