Комбинаторика и комбинаторные задачи
творческая работа учащихся (алгебра, 7 класс) по теме

Введение

"Число, положение и комбинация -

три взаимно пересекающиеся, но

различные сферы мысли, к которым

можно отнести все математические

идеи".

                     Дж. Сильвестр (1844 г.)

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

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

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

Объект исследования: область математики – комбинаторика.

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

Гипотеза: комбинаторика имеет широкий спектр практической направленности.

Задачи исследования: 

- собрать, изучить и систематизировать материал о комбинаторике;

- рассмотреть, как элементы комбинаторики используются при решении различных жизненных ситуаций;

 - использование комбинаторики в различных сферах жизнедеятельности.

Содержание

I.    Введение.

II.  Понятие о науке «Комбинаторика».

III. Основы комбинаторики.

      3.1 Размещения.

      3.2 Перестановки.

      3.3 Сочетания.

      3.4 Практическая часть.

      3.5 Задача «Замок с секретом».

IV. Комбинаторика в различных областях жизнедеятельности.

      4.1 Комбинаторика в литературе.

     4.2 Математика на шахматной доске и в играх.

     4.3 Пароли и коды в нашей жизни.

     4.4 Мебельная комбинаторика.

V.  Заключение.

Понятие о науке «Комбинаторика».

"Вперёд поедешь — голову сложишь,

  направо поедешь — коня потеряешь,

  налево поедешь — меча лишишься".

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

В знаменитой басне Крылова «Квартет» «Проказница Мартышка, Осёл, Козёл да косолапый Мишка» устроили любопытный эксперимент, они исследовали влияние взаимного расположения музыкантов на качество исполнения. И если бы не вмешался Соловей, участники квартета, наверное, перепробовали бы все возможные варианты.

Зададимся вопросом: сколько существует способов, чтобы рассадить, например в один ряд, четырех музыкантов?

Другой случай. Воспетый Маяковским «молоткастый» советский паспорт имел серию и номер, состоящие в общей сложности из трёх частей:

1. Некоторое число, записанное римскими цифрами;
2. Две русские буквы;
3. Шесть арабских цифр.

Например, IV - АВ № 057982. Разумеется, все паспорта должны иметь разные номера. Сколько может быть различных паспортов?

 Третья ситуация. Нас приглашают сыграть в Лото-Миллион. Суть игры в том, что нужно из 49 номеров угадать 6, которые выпадут во время тиража. Для участия в игре следует приобрести специальную карточку и вычеркнуть в ней 6 любых квадратов, пронумерованных числами от 1 до 49. Чтобы выиграть наверняка, можно было бы запастись таким количеством карточек, какое необходимо для вычеркивания 6 номеров всеми возможными способами. Сколько этих способов?

Общее у всех трёх задач то, что их решением занимается отдельная область математики, называемая комбинаторикой. «Особая примета» комбинаторных задач – вопрос, который всегда можно сформулировать так, чтобы он начинался словами: «Сколькими способами».

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

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

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

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

Неосновательно было бы думать, что такие древние полководцы, как Александр Македонский или Дмитрий Донской, готовясь к сражению, уповали только на доблесть и искусство воинов.

Несомненно, они на основании наблюдений и опыта военного руководства умели как-то оценить вероятность своего возвращения со щитом или на щите, знали, когда принимать бой, когда уклониться от него. Они не были рабами случая, но вместе с тем, они были ещё очень далеки от  комбинаторики и теории вероятностей.

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

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

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

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

      Как раздел математики комбинаторика возникла в XVI веке, так как для решения вероятностных задач необходимо было подсчитать число различных комбинаций элементов.  Первые научные исследования по комбинаторике принадлежат итальянским ученым Дж. Кардано, Н. Тарталье (ок. 1499-1557 гг.), Г. Галилею (1564-1642 гг.)   Дальнейшее развитие комбинаторики связано с трудами Б. Паскаля (1623 – 1662 гг.) и П. Ферма (1601 – 1665 гг.) по теории азартных игр. Позднее крупный вклад в развитие комбинаторных методов был сделан Г. Лейбницем (1646 – 1716 гг.), Я. Бернулли (1654 – 1705 гг.) и Л. Эйлером (1707 – 1783 гг.). В их работах были даны определения основных понятий комбинаторики, развиты первые комбинаторные методы и указаны их применения, а также прослежена связь комбинаторики с исчислением вероятностей. Именно комбинаторика послужила фундаментальной основой началам теории вероятностей. Немецкий учёный Г.Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666 г., впервые выделил комбинаторику как самостоятельный раздел математики. Он также впервые ввел термин «комбинаторика».

Возрождение интереса к комбинаторике относится к 50-м годам XX века. Это связано с развитием кибернетики и дискретной математики. Возможность использовать ЭВМ активизировала интерес к классическим комбинаторным задачам.

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

       В жизни каждый из нас часто сталкивается с задачами о подсчёте числа комбинаций, составленных из некоторых элементов по определённым правилам. Начнём с нескольких примеров, типичных для комбинаторики задач.

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

Решение: 

     Так как по условию задачи каждый учащийся может быть избран старостой, то, очевидно, существует 30 способов выбора старосты. Физоргом может стать каждый из  оставшихся 29 человек. Любой из 30 способов выбора старосты может осуществляться вместе с любым из 29 способов выбора физорга. Поэтому существует 30 · 29 = 870 способов выбора старосты и физорга.

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

 Задача 2.  Для дежурства в классе в течение недели (кроме воскресенья) выделены 6 учащихся. Сколькими способами можно установить очерёдность дежурств, если каждый учащийся дежурит один раз?

Решение: 

      В понедельник может дежурить любой из выделенных шести человек. Во вторник может дежурить каждый из ещё не дежуривших пяти учащихся. Следовательно, расписание дежурств на первые два дня недели можно составить 6 · 8 = 30 способами. К среде остаются четыре человека, которые ещё не дежурили, и поэтому на среду дежурного можно будет назначать 4 способами. Каждый из этих способов может комбинироваться с любым из 30 способов выбора дежурных на понедельник и вторник. Таким образом, существует 6 · 5 · 4 = 120 способов установления очерёдности дежурств на первую половину недели. В четверг сможет дежурить любой из трёх ещё не дежуривших учащихся, в пятницу – любой из двух ещё не дежуривших. К субботе выбора не будет, так как останется один человек, который ещё не дежурил. Он и будет дежурным в субботу. Ясно, что число способов, которыми можно установить очерёдность дежурств, равно

                                                          6· 5 · 4 · 3 · 2 · 1 = 720.

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

Задача 3. Для проведения экзамена создаётся комиссия из двух преподавателей. Сколько различных комиссий можно составить из пяти преподавателей?

Решение: 

      Обозначим для удобства преподавателей буквами А, В, С, Д, Е. Теперь выпишем все возможные варианты состава комиссии, а именно:

                                                                       АВ, АС, АД, АЕ,

                                                 ВС, ВД, ВЕ,

                                                   СД, СЕ,

                                                           ДЕ.

Таким образом, видно, что число различных комиссий равно 10.

        Ответ: 10 составов комиссий.

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

Задача, в которых идет речь о тех или иных комбинациях объектов, называются комбинаторными. Область математики, в которой изучаются комбинаторные задачи, называются комбинаторикой. Комбинаторику можно рассматривать как часть теории множеств – любую комбинаторную задачу можно свести к задаче о конечных множествах и их отображениях.

Размещения.

      Пусть имеется множество, содержащее n элементов. Каждое упорядоченное подмножество, состоящее из k элементов, называется размещением из n элементов по k элементов.

      Из определения вытекает, что n ≥ k ≥ 0 и что размещения из n элементов по k элементов – это всё k – элементные подмножества, отличающиеся составом элементов или порядком их следования. Для множества, состоящего из 4–х элементов а, б, с, д, размещения по 3 элемента составляют: 24 варианта, и они отличаются друг от друга либо составом элементов, либо порядком их расположения.  

      В комбинаторных задачах необходимо уметь подсчитывать число всех возможных размещений из n элементов по k элементов. Для обозначения этого числа применяется специальный символ Аnk  (читается: «число размещений из n по k» или «А из n по k»).

      А – первая буква французского слова arrangement, что означает размещение, приведение в порядок. Следовательно, в задаче 1 требовалось найти число размещений из 30 элементов по 2 элемента, и из решения этой задачи следует, что А302 = 870.Также следует помнить, что Аn0 = 1, так как существует только одно подмножество n- элементного множества, не содержащее элементов (пустое множество).

      В общем случае на вопрос о числе размещений из n элементов по k элементов даёт ответ следующая формула:

Аnk  = n (n – 1) (n – 2) …(n – k + 1),  k› 0,               (1)

т.е. число размещений из n элементов по k элементов равно произведению k последовательных натуральных чисел от n до n – k + 1 включительно.

       Число размещений из n элементов по k элементов равно числу всех k – элементных упорядоченных подмножеств множества, содержащего n элементов. Первый элемент подмножества можно, очевидно, выбрать n способами, второй элемент подмножества можно выбрать уже только n – 1 способом, так как в качестве второго элемента можно взять любой элемент множества, кроме уже выбранного первым. Каждый из способов выбора первого элемента может объединиться с каждым из способов выбора второго, и следовательно, существует n(n – 1) способов выбора первых двух элементов при построении k-элементного упорядоченного подмножества. После выбора первых двух элементов остаются n – 2 возможности для выбора третьего элемента, и каждая из этих возможностей может комбинироваться с любой из возможностей выбора первых двух элементов, т.е. выбор первых трёх элементов может быть осуществлён n(n – 1)(n – 2) способами. Последний k-й элемент k-элементного подмножества может быть выбран

n – k + 1 способом, так как к моменту выбора k-го элемента осталось n – (k – 1) элементов.

      Произведение всех натуральных чисел от n до единицы, обозначают символом n! (читается «эн факториал»). Используя знак факториала, можно, например, записать:

                                1! = 1,

                                2! = 2∙1 = 2,

                                3! = 3 ∙2 ∙1 = 6,

                                4! = 4 ∙3 ∙2 ∙1 = 24,

                                        5! = 5 ∙4 ∙3 ∙2 ∙1 = 120.

      Для нахождения числа размещений из n элементов по k элементов можно также применять следующую формулу:

                                n(n - 1)(n - 2)…(n – k + 1)(n - k)!

                  A kn  =                    (n - k)!

или                                  n!

                Akn       =      (n - k)!                                                (2)

Формулой (2) можно пользоваться при k = 0, так как она в этом частном случае даёт следующий результат:

                                 n!                

                        A0n=  (n - 0)!        =   n!/ n! =1

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

Решение: Различных способов составления расписания, очевидно, столько, сколько существует пятиэлементных упорядоченных подмножеств у четырнадцатиэлементного множества. Следовательно, число способов равно числу размещений из 14 элементов по 5, т.е. равно А145. По формуле (1), полагая в ней n = 14, k = 5, находим

                                             А145 = 14 ∙13 ∙12 ∙11 ∙10 = 240240.

                                                                                                                                            Ответ: 240 240 вариантов расписания.

Задача 5. Сколькими способами можно изготовить 3-х цветный флаг с горизонтальными полосами, если имеется материал 7-ми цветов.

Решение:  А73 = 7(7 – 1) (7 – (3 – 1)) = 7 ∙6 ∙5 = 210 способов.

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

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

Решение: Всевозможные комбинации выходящих друг за другом трёх из четырёх пассажиров купе образуют размещения из четырёх элементов по три. Общее число  таких размещений обозначается А43.

Так как в каждом размещении на первом месте может быть любой из четырёх пассажиров, на втором – любой из трёх оставшихся, а на третьем – любой из двух оставшихся (после того как из купе уже вышли двое), то всевозможных комбинаций из четырёх пассажиров по три при учёте порядка следования пассажиров будет  4 ∙3 ∙2 = 24, т.е.

                                А43 = 4 ∙3 ∙2 = 24.

                                Ответ: 24 варианта выхода из вагона.                                                                                                                          

 Задача 7. Сколько различных двузначных чисел можно составить из цифр 1, 2, 3, 4, 5, 6, 7, 8 при условии, что в записи числа каждая цифра используется только один раз?

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

                                А82 = 8 (8 – 1) = 8 ∙7 = 56.

                                                Ответ:  56 двузначных чисел.

Перестановки.

      Размещения из n элементов по n элементов называются перестановками из n элементов.

      Перестановки являются частным случаем размещений. Так как каждая перестановка содержит все n элементов множества, то различные перестановки отличаются друг от друга только порядком элементов. Число перестановок из n элементов обозначают через Рn. Р – первая буква французского слова permutation – перестановка.

      В общем случае число перестановок из n элементов Рn = Аnn, и следовательно, его можно найти по формуле (1) или по формуле (2), положив в каждой из них k = n. Действительно, формула (2) даёт

                                n!            n!

                Рn = Аnn  =  (n – n)! =  0! = n!,

Из формулы (1) находим

                        Рn = Аnn  = n (n – 1) (n – 2) …(n – n + 1) = n!.

Итак, число перестановок из n элементов равно n!

      Таким образом в множестве, содержащем n элементов, установить определённый порядок следования элементов или, как говорят, упорядочить такое множество можно n! способами.

      Например, список учеников класса, в котором 20 человек и нет однофамильцев, можно составить

                       20! = 2 432 902 008 176 640 000 способами.

Задача 8. Сколько различных перестановок можно образовать из букв слова  «задача»?

Решение: Образовать какую – либо перестановку из букв слова «задача» - это значит на шесть занумерованных мест, каким – нибудь образом поставить одну букву «з», одну букву «д», одну букву «ч» и три буквы «а». Если буквы «з», «д» и «ч» как – то поставлены, то остальные места заполняются буквами «а». Но сколькими способами можно поставить три различные буквы на шесть мест? Очевидно, что число способов равно числу всех трёхэлементных упорядоченных подмножеств шестиэлементного множества, т.е. равно

                                        А63 = 6 ∙5 ∙4 = 120.

                                        Ответ:  120 различных перестановок.

      Можно рассуждать и иначе. Если бы все шесть букв слова были различны, то число перестановок было бы равно 6!. Но буква «а» встречается в данном слове три раза, и перестановки только этих трёх букв «а» не дают новых способов расположения букв. Поэтому число перестановок букв в слове «задача»  будет не 6!, а в 3! раз меньше, т.е.

                        6!        6∙5∙4∙3∙2∙1

                        3!  =                    3∙2∙1               = 6∙5∙4= 120.

Задача 9. Сколькими способами можно разместить на полке 5 книг?

Решение: Задача сводится к подсчёту числа перестановок из пяти элементов:

                  Р5 = 5! = 1 ∙2 ∙3 ∙4 ∙5 = 120 способов.                                                                                                                                            

                                                Ответ: 120 способов

 Задача 10. Сколькими способами могут быть расставлены 8 участниц финального забега на 8-ми беговых дорожках?  

 Решение:   Р8 = 8!= 1 ∙2 ∙3 ∙4 ∙5 ∙ 6 ∙7 ∙8 = 40320 способов.  

                                                                                                      Ответ: 40320 способов забега. 

Сочетания.

      Пусть имеется множество, состоящее из n элементов. Каждое его подмножество, содержащее k элементов, называется сочетанием из n элементов по k элементов.

      Сочетания из n элементов по k элементов – это все k-элементные подмножества n-элементного множества, причём различными подмножествами считаются только те, которые имеют неодинаковый состав элементов. Подмножества, отличающиеся друг от друга только порядком следования элементов, не считаются различными. Например, для четырёхэлементного множества a, b, c, d  сочетаниями по 3 элемента являются следующие подмножества:

                        abc,       abd,     acd,     bcd.

      Число всех сочетаний из n элементов по k элементов обозначается символом Сnk (читается: «число сочетаний из n по k»). С – первая буква французского слова combinasion – сочетание. Число сочетаний из 5 элементов по 2 элемента будет С52 = 10.

      В общем случае число сочетаний из n элементов по k элементов определяется следующей формулой:

                              n!

                                      Сkn =  (n - k)! k!

      Формулу (3) можно записать в другом, более удобном для вычислений виде:

                                                          n (n - 1) (n - 2)…( n – k + 1)                        (4)        

                                        Сkn =                          k!

т.е. число сочетаний из nэлементов по k элементов равно произведению всех натуральных чисел от n до n – k + 1 включительно, делённому на k!

Задача 11. Сколько экзаменационных комиссий, состоящих из 7 членов, можно образовать из 14 преподавателей?

Решение:  Очевидно, столько, сколько существует семиэлементных подмножеств у четырнадцатиэлементного множества. По формуле (4)находим

        14∙13∙12∙11∙10∙9∙8   14∙13∙12∙11∙10∙9∙8

                  С714  =                                 7!                            =       7∙6∙5∙4∙3∙2∙1        = 3432.

Задача 12. В чемпионате страны по футболу (высшая лига)  участвуют 18 команд, причём каждые две команды встречаются между собой 2 раза. Сколько матчей играется в течение сезона?

Решение: В первом круге состоится столько матчей, сколько существует двухэлементных подмножеств у множества, содержащего 18 элементов, т.е. их число равно С182. По формуле (4) получаем

                                 18∙17

                        С218 =              2       =153.

      Во втором круге играется столько же матчей, поэтому в течение сезона состоится 306 встреч.

                                                                                         Ответ: 306 встреч. 

Задачи.

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

Решение: Девушку из состава кружка можно выбрать пятью способами, а юношу – тремя. Пару (девушка с юношей) можно выбрать пятнадцатью различными способами

5 ∙3 = 15 способов.

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

Задача 14. Сколько различных трёхзначных чисел можно составить из цифр 0, 1, 2, 3, 4?

Решение: Первой цифрой трёхзначного числа может быть одна из четырёх цифр 1, 2, 3, 4, а второй и третьей – любая из пяти цифр 0,1, 2, 3, 4. Всего можно образовать

                                4 ∙5 ∙ 5 = 100 трёхзначных чисел.

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

Задача 14. Андрей, Борис, Владимир, Григорий, Дмитрий и Евгений при встрече обменялись каждый  с каждым рукопожатием. Сколько всего было сделано рукопожатий?

Решение: Обозначим для удобства  юношей буквами А, Б, В, Г, Д, Е. Теперь выпишем все возможные варианты рукопожатий, а именно:

                                                                       АБ, АВ, АГ, АД, АЕ,

                                                 БВ,  БГ, БД, БЕ,

                                                    ВГ, ВД, ВЕ,

                                                           ГД, ГЕ,

                                                              ДЕ.                

Таким образом, видно, что число различных рукопожатий  равно 15.    

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

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

Решение: В соответствии с правилом произведения всего можно составить 5 ∙6 = 30 подарков.

                                                                                 Ответ: 30 подарков.

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

 Решение: 8 ∙6 = 48 пар.

                                                                     Ответ: 48 пар.

Задача 17. Путешественник из пункта А в пункт С может попасть, доехав до промежуточного пункта В по одной из трёх существующих автомагистралей, а из В в С доехать либо поездом, либо на такси. Сколько существует различных маршрутов между пунктами А и С?

Решение: 3 ∙2 = 6 маршрутов.

                                                                       Ответ: 6 маршрутов.

Задача 18. Сколько различных четырёхзначных чисел можно составить из цифр 1, 2, 3, 4?

Решение: Первой цифрой четырёхзначного числа может быть одна из четырёх цифр 1, 2, 3, 4, а второй, третьей и четвёртой -  также любая из этих цифр. В соответствии с правилом произведения всего можно образовать

                        4 ∙4 ∙4 ∙4 = 256 четырёхзначных чисел.

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

Задача 19. В соревновании участвуют 10 команд. Сколько существует вариантов распределения призовых (1, 2, 3) мест?

  Решение: А103 = 10 ∙9 ∙8 = 720 вариантов распределения призовых мест.

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

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

Решение: Первым в очередь мог встать любой девятиклассник, вторым – любой из оставшихся троих, третьим – любой из оставшихся двоих и четвёртым – девятиклассник, подбежавший последним. По правилу умножения у четверых ребят существует 4321=24 способа занять очередь.

                                                                                                             Ответ: 24 способа.

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

Решение: Общее количество предметов по правилу умножения равно: 3  4  3  2 = 72.

Ответ: 72 различных костюма.  

Задача 22.  Олеся, Оксана и Юля купили билеты на концерт симфонического оркестра на 1, 2 и 3-е места первого ряда. Сколько существует способов размещения девочек на эти места?

Решение: Количество различных способов равно числу перестановок из 3 элементов:

Р3 = 3! = 123 = 6 способов.

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

Задача 23.  Сергей, Игорь и Миша могут занять 1-е, 2-е и 3-е призовые места в соревнованиях по шахматам. Перечислить всевозможные последовательности из имён мальчиков, где порядковый номер в последовательности соответствует занятому мальчиком месту в соревнованиях. Подсчитать их количество.

Решение: Сначала выбираем одного на первое место, а двух других меняем местами, потом берём на первое место другого и т.д.:

                                                                     СИМ; СМИ;

                                                                     ИСМ; ИМС;

                                                                     МСИ; МИС.

 Всего 6 вариантов расположения.

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

Задача 24.  В школьной столовой имеются помидоры, огурцы и лук. Сколько различных салатов можно приготовить, если в каждый из них должны входить в равных долях 2 различных вида овощей? Записать все сочетания овощей в составленных салатах.

Решение: Расположим данные овощи по порядку: помидоры, огурцы, лук. Запишем все сочетания овощей в салатах. Будем брать поочерёдно каждый овощ (кроме последнего) и добавлять к нему по одному, только из последующих, поскольку порядок выбора не важен:                                         1) помидоры, огурцы;

                                                2) помидоры, лук;

                                                3) огурцы, лук.                                 

                                                                        Ответ: 3 вида салатов.

Задача 25.  На соревнованиях по лёгкой атлетике нашу школу представляла команда из 10 спортсменов. Сколькими способами тренер может определить, кто из них побежит в эстафете 4100 м на первом, втором, третьем и четвёртом этапах?

Решение: Выбор из 10 по 4 с учётом порядка:  способов.

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

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

Решение: На первое место можно поставить любой из четырех шариков (4 способа), на второе – любой из трех оставшихся (3 способа), на третье место – любой из оставшихся двух (2 способа), на четвертое место – оставшийся последний шар. Всего 4 · 3 · 2 · 1 = 24 способа.

                                              Р4 = 4! = 1 · 2 · 3 · 4 = 24.

                                                                                                                                                                Ответ: 24 способа.

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

                        Задача «Замок с секретом».

      В одном советском учреждении был обнаружен несгораемый шкаф, сохранившийся с дореволюционных лет. Отыскался и ключ к нему, но чтобы им воспользоваться, нужно было знать секрет замка; дверь шкафа открывалась лишь тогда, когда имевшиеся на двери 5 кружков с алфавитом на их ободах (36 букв) устанавливались на определённое слово. Так как никто этого слова не знал, то, чтобы не взламывать шкафа, решено было перепробовать все комбинации букв в кружках. На составление одной комбинации требовалось 3 секунды времени.

       Можно ли надеяться, что шкаф будет открыт в течение ближайших 10 рабочих дней?

Решение: Подсчитаем, сколько всего буквенных комбинаций надо было перепробовать.

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

                                        36  36 = 362.

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

                                        362  36 = 363.

      Таким же образом определяем, что четырёхбуквенных комбинаций может быть 364, а пятибуквенных 365 или 60466176. Чтобы составить эти 60 с лишним миллионов комбинаций, потребовалось бы времени, считая по 3 секунды на каждую,

                        3  60 466 176 = 181 398 528 секунд.

Это составляет  более 50 000 часов, или почти 6300 восьмичасовых рабочих дней – более 20 лет.

       Значит, шансов на то, что шкаф будет открыт в течение ближайших 10 рабочих дней, имеется 10 на 6300, или один из 630. Это очень малая вероятность.

 Комбинаторика в различных областях жизнедеятельности человека.

Комбинаторика в литературе.

 В басне Ивана Андреевича Крылова «Квартет»: «проказница Мартышка, Осёл, Козёл да косолапый Мишка» устроили любопытный эксперимент, они исследовали влияние взаимного расположения музыкантов на качество исполнения.  

                                                     Проказница-Мартышка,

                                                                   Осёл,

                                                                   Козёл

                                                   Да косолапый Мишка

                                              Затеяли сыграть Квартет.

                                       Достали нот, баса, альта, две скрипки

                                               И сели на лужок под липки —

Пленять своим искусством свет.

Ударили в смычки, дерут, а толку нет.

«Стой, братцы, стой! — кричит Мартышка. —

Погодите!

Как музыке идти? Ведь вы не так сидите.

Ты с басом, Мишенька, садись против альта,

                                    Я, прима, сяду против вторы;

Тогда пойдёт уж музыка не та:

У нас запляшут лес и горы!»

Расселись, начали Квартет;

Он всё-таки на лад нейдёт.

«Постойте ж, я сыскал секрет, —

Кричит Осёл: — мы, верно, уж поладим,

                                                             Коль рядом сядем».

Послушались Осла: уселись чинно в ряд;

А всё-таки Квартет нейдёт на лад.

Вот пуще прежнего пошли у них разборы

                                                                     И споры,

                                                          Кому и как сидеть.

Случилось Соловью на шум их прилететь.

Тут с просьбой все к нему, чтоб их решить сомненье:

«Пожалуй, — говорят: — возьми на час терпенье,

Чтобы Квартет в порядок наш привесть:

И ноты есть у нас, и инструменты есть;

                                                            Скажи лишь, как нам сесть!» —

«Чтоб музыкантом быть, так надобно уменье

И уши ваших понежней, —

Им отвечает Соловей: —

А вы, друзья, как ни садитесь,

Всё в музыканты не годитесь».

Мартышка, Осёл, Козёл и Мишка пересаживались, считая, что от этого зависит звучание музыки. И если бы не вмешался Соловей, участники квартета, наверное, перепробовали бы все возможные варианты.

Зададимся вопросом: сколько существует способов, чтобы рассадить, например в один ряд, четырех музыкантов?

Число перестановок можно посчитать по формуле:

                        Р4 = n! = 4! = 4  3  2 = 24 способа.

                                                                                                 Ответ: 24 способа.

Математика на шахматной доске и в играх.

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

Клод Шеннон и Михаил Ботвинник внесли огромный вклад в создание математической модели шахматной игры и способствовали прогрессу в интеллектуализации программ для нее.

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

Необыкновенно популярна головоломка - кубик Рубика, изобретенный в 1975 г. преподавателем архитектуры из Будапешта Эрне Рубиком для развития пространственного воображения у студентов. Задача поиска оптимального (по числу ходов) алгоритма сбора кубика Рубика является самой сложной и не решенной пока математической задачей. Представляет интерес также изучение группы, порожденной поворотами граней, и др. Кубик Рубика служит не только развлечением, но и прекрасным наглядным пособием по алгебре, комбинаторике, программированию.

Пароли и коды в нашей жизни.

Вся наша жизнь состоит из множества разнообразных программ. Чтобы запустить ту или иную программу нужно ввести соответствующий верный пароль.

В качестве кода в зависимости от рода программы могут выступать всевозможные цифры, слова или комбинации слов, поведение или действие, и так далее...

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

Мебельная комбинаторика.

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

Заключение

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

Комбинаторика имеет огромное значение в различных областях науки и сферы. С комбинаторными величинами приходится иметь дело представителям многих специальностей: ученому – химику, биологу, конструктору, диспетчеру и т.п. Комбинаторика используется в литературе, математике, музыке, в мебельной деятельности, и различных играх (нарды, шашки, шахматы). В каждой из этих игр приходится рассматривать различные сочетания фигур, и выигрывает тот, кто их лучше изучает, знает выигрышные комбинации и умеет избегать проигрышных. Усиление интереса к комбинаторике в последнее время обуславливается бурным развитием кибернетики.

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

Литература.

1. Бутузов В.Ф., Колягин Ю.М., Луканкик Г.Л., Позняк Э.Г., Сидоров Ю.М., Ткачёва М.В., Фёдорова Н.Е., Шабунин М.И. Математика. Учебное пособие для 11 классов общеобразовательных учреждений. Москва «Просвещение», 1996 год.

2. Грэхем Р., Кнут Д.А., Паташник О. Конкретная математика. Москва « Мир», 1998 год.

3. Кутасов А.Д., Пиголкина Т.С., Чехлов В.И., Яковлева Т.Х. Пособие по математике для поступающих в вузы. Москва «Наука», 1988 год.

4. Перельман Я.И. Занимательная алгебра. Занимательная геометрия. Москва, АСТ «Астрель»,2002 год.

5. Фадеев Д.К., Никулин М.С., Соколовский. Элементы высшей математики для школьников. Москва «Наука»,  1987 год.

6. Элементы теории вероятностей. Математика. Приложение к газете "Первое сентября", 1999 год,  № 41, 42.

 Описание работы:

      Работа над темой «Комбинаторика» включает в себя: историю комбинаторики, основы комбинаторики, основные формулы комбинаторики. Рассмотрены различные задачи, показаны области применения комбинаторики.