Изучение и первичное усвоение новых знаний

Допустим нас 25.

Каждый из 25-и человек пожал руки 24-м. Однако произведение 25 * 24 = 600 дает удвоенное число рукопожатий (так как в этом расчете учтено, что первый пожал руку второму, а затем второй первому, на самом же деле было одно рукопожатие). Итак, число рукопожатий равно: (25 * 24): 2 = 300.

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

· Сколькими способами…?

· Сколько вариантов…?

Изучение и первичное усвоение новых знаний.

·  «Что такое комбинаторика? Истоки комбинаторики»

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

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

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

Комбинаторика - раздел математики, в котором изучаются простейшие «соединения». Перестановки - соединения, которые можно составить из n предметов, меняя всеми возможными способами их порядок; число их Размещения - соединения, содержащие по m предметов из числа n данных, различающиеся либо порядком предметов, либо самими предметами; число их Сочетания - соединения, содержащие по m предметов из n, различающиеся друг от друга, по крайней мере, одним предметом (в современном толковом словаре изд. «Большая Советская Энциклопедия»).

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

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

Первоначально комбинаторика возникла в XVI в в связи с распространением различных азартных игр. 

Основы комбинаторики и теории вероятностей создали и разработали французские математики XVII века Пьер Ферма и Блез Паскаль.

Комбинаторные мотивы можно заметить в символике китайской «Книги Перемен» (V век до н. э.). По мнению её авторов, всё в мире комбинируется из различных сочетаний мужского и женского начал, а также восьми стихий: земля, горы, вода, ветер, гроза, огонь, облака и небо. Историки отмечают также комбинаторные проблемы в руководствах по игре в Го и другие игры. Большой интерес математиков многих стран с древних времён неизменно вызывали магические квадраты. 

В XII веке индийский математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями.

В Западной Европе ряд глубоких открытий в области комбинаторики сделали два еврейских исследователя, Авраам ибн Эзра (XII век) и Леви бен Гершом (он же Герсонид, XIV век). Ибн Эзра обнаружил симметричность биномиальных коэффициентов, а Герсонид дал явные формулы для их подсчёта и применения в задачах вычисления числа размещений и сочетаний.

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

Помимо азартных игр, комбинаторные методы использовались (и продолжают использоваться) в криптографии — как для разработки шифров, так и для их взлома.

Ученик Лейбница Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713) множество сведений по комбинаторике.

В этот же период формируется терминология новой науки. Термин «сочетание» впервые встречается у Паскаля. Термин «перестановка» употребил в указанной книге Якоб Бернулли. Бернулли использовал и термин «размещение».

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

· «Комбинаторика в реальной жизни»

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

                                П. Лаплас

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

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

Области применения комбинаторики:

• учебные заведения (составление расписаний)

• сфера общественного питания (составление меню)

• лингвистика (рассмотрение вариантов комбинаций букв)

• география (раскраска карт)

• спортивные соревнования (расчёт количества игр между участниками)

• производство (распределение нескольких видов работ между рабочими)

• агротехника (размещение посевов на нескольких полях)

• азартные игры (подсчёт частоты выигрышей)

• химия (анализ возможных связей между химическими элементами)

• экономика (анализ вариантов купли-продажи акций)

• криптография (разработка методов шифрования)

• доставка почты (рассмотрение вариантов пересылки)

2 «Решение комбинаторных задач»

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

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

Задача 1. Майор Зимин ежедневно формирует наряд для поддержания общественного порядка в городе. Наряд состоит из двух человек: старшего наряда и дежурного. В расположении майора находится 20 полицейских. На сколько дней подряд майор Зимин составит график?

Решение. Пусть сначала избирается старший наряда. Поскольку каждый полицейский может быть выбран старшим, то, очевидно, есть 20 способов его выбора. Тогда дежурным может стать каждый из оставшихся 19 полицейских. Любой из 20 способов выбора старшего наряда может осуществиться вместе с любыми из 19 способов выбора дежурного. Поэтому всего существует 20 ∙ 19 = 380 способов формирования наряда. Т.о. на 380 дней майор Зимин может составить график.

  Задача 2. В отделении сержанта Сбруева проходят службу 4 новобранца: Белкин, Пенкин, Свечкин и Овечкин. В свободное от нарядов время сержант обучает их, как рассчитаться по порядку. По команде «В одну шеренгу становись!» солдаты выстраиваются справа от Сбруева и по команде «По порядку номеров рассчитайсь!» производят расчет: «первый-второй-третий-четвертый-пятый». После этого сержант перестраивает но­вобранцев по-новому и расчет повторяется. Сколько раз может Сбруев повторить это упражнение, используя только разные способы построения солдат?

1

2

3

4

3

4

4

3

2

4

4

2

2

3

2

3

Решение. Первого новобранца стоящего в шеренге можно выделить четырьмя способами; второго, очевидно, тремя способами. На третье место будут претендовать только два человека, и, следовательно, есть два способа заполнить третье место. Для четвертого новобранца  места уже не остается, и он выступает последним.

Занумеруем новобранцев: 1 – Белкин, 2 – Пенкин, 3 – Свечкин, 4 – Овечкин.

Составим схему.

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

4 ∙ 6 = 24.

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

Решение. Обозначим книги буквами A, B, C, D, E, можно выписать все возможные пары книг, а именно: AB, AC, AD, AE, BC, BD, BE, CD, CE, DE. Мы видим, что их число равно десяти.