Комбинаторика

Курс по выбору «Комбинаторика» Урок № 1. Тема:    Введение в комбинаторику. Танграм. Методы решения  комбинаторных задач.     Цель занятия: Познакомить учащихся  со структурой курса. Требования к  учащимся. Дать  понятие комбинаторных задач. Научить строить  «дерево вариантов» Наглядность и раздаточный материал:  Презентация №1. Портреты учёных­ математиков. Танграм и фигурки из него. Тест №1. Карточки  с  задачами.  Оргмомент.  1. Требования к учащимся: завести тетрадь, выполнять  домашние задания, выполнение самостоятельных работ, в конце курса – написание и защита реферата (объём от 3 до 5 листов) 2. Темы рефератов:   Танграм  Магические квадраты  Латинские квадраты  Факториал  Перестановки   Размещения  Сочетания  Бином Ньютона        1. Что изучает комбинаторика? При решении многих практических задач приходится выбирать из некоторой  совокупности объектов элементы, располагая их в определённом порядке.  Например: 1) 5 друзей решили сфотографироваться. Сколькими способами они могут сесть? 2) В столовой имеются 2 салата, 3 вторых, 4 напитка. Сколько вариантов  обедов можно составить? 3) В классе 25 учеников. На городскую ёлку нужно выбрать 2 человек.  Сколькими способами это можно сделать? 4) В басне И.А. Крылова «Квартет»:  Проказница­мартышка, Осёл, Козёл, да косолапый Мишка затеяли  сыграть квартет. И так садились, и эдак, а толку нет… А сколько же  способов их рассадить существует? 1 В этих задачах речь идёт о комбинациях объектов. Такие задачи  называются комбинаторными. Комбинаторика – это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов.  Термин «комбинаторика» происходит от латинского слова combina ­ сочетать, соединять.   Комбинаторика   занимается   различного   рода   сочетаниями (соединениями),   которые   можно   образовать   из   элементов   некоторого конечного множества.  Выбором объектов и их расположением приходится заниматься чуть ли не  во   всех   областях   человеческой   деятельности  –  конструктору,  учёному­ генетику,   агроному,   составителю   кодов,   лотерей,   химику,   комбинаторные задачи применяются при игре в шашки, шахматы, при подсчёте вариантов в теории вероятностей и т.д.  2. Исторический обзор. С комбинаторными задачами люди сталкивались с глубокой древности. В Древнем   Китае   увлекались   составлением   математических   головоломок (магические   квадраты),   в   Древней   Греции   составляли   геометрические головоломки   на   разрезание   и   складывание   фигур   (до   наших   дней   дошла головоломка «Пифагор»).  Термин «комбинаторика» был введён в математический обиход Лейбницем. Готфрид Вильгельм фон Лейбниц (1646 ­  1716 г.г.) немецкий философ и математик. Многие   называют   его   последним ученым   эпохи   Возрождения,   или первым   ученым   эпохи   Просвещения. До наших дней никто иной не сочетал столь яркий математический талант с такой   широтой   гуманитарных склонностей.   В   этом   отношении Лейбница   можно   сравнить   с Аристотелем,   с   Леонардо   да   Винчи или   Рене   Декартом.   В   8   лет   он самостоятельно изучил латынь, а еще через   два   года   —   древнегреческий язык. Тяга к экзотическим языкам не исчезла и позднее: познакомившись с элементами   персидского   языка   и хинди,   Лейбниц   одним   из   первых 2 высказал   догадку   об   индоевропейской   языковой   общности,   за   которой скрываются какие­то переселения древнейших народов.  Лейбниц, наряду с  Ньютоном, создатель  математического анализа  — дифференциального и интегрального исчисления.   Лейбниц также ввёл бинарную систему счисления с цифрами 0 и 1, на котором базируется современная компьютерная техника.  Лейбниц   создал  механический   калькулятор,   выполняющий  сложение, вычитание,   Машина   была продемонстрирована   во  Французской   академии   наук  и   лондонском Королевском обществе.  умножение   деление  чисел. и  В 1666 г. он опубликовал «Рассуждения о комбинаторном искусстве», в которой   рассмотрел   вопросы   сочетаний   элементов,   рассмотрел применение комбинаторики в арифметике, логике, в стихосложении. В течение   своей   жизни   Лейбниц   неоднократно   обращался   к   вопросам комбинаторики. Мечтой его жизни, оставшейся, увы, неосуществлённой, оставалось построение общей комбинаторной теории.  В  XVIII  веке   к   решению   комбинаторных   задач   обращались   многие выдающиеся   ученые­математики.   В   1713   г.   было   опубликовано   сочинение Якова   Бернулли  «Искусство   предположений»,   в   котором   с   достаточной полнотой   были   изложены   и   обобщены     известные   к   тому   времени комбинаторные   факты.   Это   сочинение   отличалось   полнотой   и   строгостью изложения,   доступностью.   Оно   являлось   учебно­справочным   изданием   по комбинаторике на протяжении двух столетий.  Леонард Эйлер рассматривал задачи о разбиении чисел, о паросочетаниях, о  циклических расстановках, о  построении магических и латинских  квадратов.                       Леонард Эйлер (1707  ­  1783  г.г.)   —   выдающийся математик,   родился   в   Швейцарии, жил   и   работал   в   России.   Внёс значительный   вклад   в   развитие математики,   а   также  механики, и   ряда  астрономии  физики, прикладных наук.   Эйлер принадлежит   к   числу   гениев,   чьё творчество   стало   достоянием   всего человечества. До сих пор школьники всех стран изучают  тригонометрию  и логарифмы в том виде, какой придал   Студенты   проходят им   Эйлер. высшую   по математику     3 руководствам, монографии Эйлера.    первыми   образцами   которых   явились   классические В XX веке комбинаторика подверглась мощному процессу алгебраизации благодаря работам Дж. К. Рота, а затем Р. Стенли.  В настоящее время комбинаторику начинают изучать с начальной школы.  3. Геометрические комбинации Танграм   –   древнекитайская   головоломка.   Это   квадрат,   разрезанный определённым образом на 7 частей.  Упражнения.  На каждой парте разрезанный Танграм. Учащимся предлагается собрать по  образцу несколько фигурок.  Даётся разъяснение о написании реферата по теме Танграм. 4. Логический тест. 5. Методы решения комбинаторных задач 4 Задача. Дано множество чисел {1,2,3,4}. Составьте: а) двузначные числа б) четырёхзначные числа Решение: Метод перебора: двузначные числа – 12,  13,  14,                                                                   21,  23,  24,                                                                  31,  32,  34,                                                                  41,  42,  43. Всего 12 чисел. «Дерево вариантов»:                                                                          1234                                                                        1243                                                                      1324                  6 чисел                                                                      1342                                                                                     1423                                                                      1432                                                                        Всего четырёхзначных чисел 4∙ 3 ∙ 2 ∙ 1 = 24 Упражнения. 1. Коля, Боря, Вова и Юра заняли 1, 2, 3 и 4 место на соревновании. Известно, что у Коли ни 1, ни 4 место. Боря занял 2 место. Вова не последний. Какое место у каждого мальчика? Коля Боря Вова Юра 1 ­ ­ + ­ 2 ­ + ­ ­ 3 + ­ ­ 4 ­ ­ ­ + 2. Петя и Вася пишут контрольную по математике. Каждый может  получить любую из оценок 2,3,4,5. Сколько существует вариантов  получения ими оценок? П2 В2    П2 В3     П2 В4     П2 В5  5 П3 В2    П3 В3     П3 В4     П3 В5 П4 В2    П4 В3     П4 В4     П4 В5 П5 В2    П5 В3     П5 В4     П5 В5,  всего 16 вариантов. Домашнее задание:   Составить числа из 5 двоек  Составить фигурки из Танграма  Решить задачи: 1) Сколькими способами можно выложить в ряд 2 белых и 2 чёрных  шарика? 2) В вазе лежат яблоко, груша, персик и абрикос. Маше разрешили  взять два каких­либо фрукта. Сколько у Маши вариантов выбора? 3) У Ани 4 платья и 3 пары туфель. Собираясь на вечеринку, она  думает, что бы ей надеть. Сколько всего у Ани вариантов? 4) В Норильске, Москве, Ростове и Пятигорске живут 4 супружеские  пары. Имена этих супругов: Антон, Борис, Давид, Григорий, Ольга,  Мария, Светлана, Екатерина. Известно, что ­ Антон живёт в Норильске; ­ Борис и Ольга супруги; ­ Григорий и Светлана не живут в одном городе4 ­ Мария живёт в Москве; ­ Светлана – ростовчанка. Кто на ком женат и кто где проживает? 6