Участники проекта: учащиеся 11 класса
Тип проекта: практически-ориентированный
Срок выполнения: 2 недели
Эпиграф урока: «Число, размещения и комбинация – три взаимнопересекающихся, но разных сферы мысли, которыми можно описать все математические идеи». (Д.Д. Сильвестр)
Развивать творческое мышление всесторонним анализом проблем, запоминать информацию в виде логических структур, понимать причинно-следственные связи.
Проекты можно подавать в форме презентаций или рефератов.
Тип урока: урок обобщения и систематизации знаний.
2. Просмотр проекта «История возникновения и развития науки комбинаторики».
Ориентировочный опорный конспект проектаКомбинаторика - ветвь математики, изучающая комбинации и перестановки предметов - возникла в XVII в. С задачами, в которых приходится выбирать те или иные предметы, размещать их в определенном порядке и отыскивать среди различных размещений лучшие, люди столкнулись еще в доисторическую эпоху, выбирая лучшие размещения охотников во время охоты, воинов во время битвы, инструментов во время работы . Определенным образом располагались украшения на одежде, узоры на керамике. С усложнением производственных и общественных отношений шире приходилось пользоваться общими понятиями о порядке, иерархии, группировке. В том же направлении действовало развитие ремесел торговли. Комбинаторные навыки оказались полезными и в часы досуга. Нельзя точно сказать, когда рядом с соревнованиями по бегу, метанию диска, прыжках появились игры, которые нуждались в первую очередь в умении рассчитывать, составлять планы и опровергать планы противника.
Комбинаторика в ЕгиптеСреди предметов, положенных в пирамиду, где 35 веков назад был похоронен египетский фараон Тутанхамон, нашли расчерченную дощечку с тремя горизонталями и 10 вертикалями и фигурки для древней игры «сенет», о правилах которой мы, возможно, никогда не узнаем . Впоследствии появились нарды, шашки и шахматы, а также их различные варианты (китайские и японские шахматы, японские облавные шашки «го» и др.). В каждой из этих игр приходилось рассматривать различные комбинации фигур, имевших способность передвигаться, и выигрывал тот, кто их лучше изучил, знал выигрышные комбинации и умел избегать проигрышей. Конечно, в этот период никто и не догадывался о науке, которая рассматривает решение комбинаторных задач.
Комбинаторика в Китае
Первое упоминание о вопросах, близких к комбинаторным, встречается в китайских рукописях, относящихся к XII-XIII вв. до н. э. В этих книгах написано, что все в мире является сочетанием двух начал - мужского и женского, которые авторы обозначали символами «инь» и «янь». В рукописи «Же-ким» («Книга перемен») показаны различные соединения этих знаков по два и по три. Восемь рисунков из трех рядов символов отражали землю, горы, воду, ветер, грозу, огонь, облака и небо. Сумма первых 8 натуральных чисел (то есть число 36) воплощала в воображении древних китайцев весь мир. Впоследствии возникла потребность выразить и другие элементы с помощью знаков «инь» и «янь». Были составлены 64 фигуры, состоящие из пяти рядов черточек.
В рукописи «Же-ким» есть и более сложные рисунки. Как утверждает легенда, император Ию, живший примерно 4000 лет назад, увидел на берегу реки священную черепаху, на панцире которой был изображен рисунок из белых и черных кружков. Если заменить каждую фигуру соответствующим числом, появляется такая таблица, где при добавлении чисел в каждой строке, столбике и по диагонали получим одно и то же число 15.
Комбинаторика в Древней Греции
Конкретные комбинаторные задачи, которые касались пересчета небольших групп предметов, греки решали без ошибок. Аристотель описал без пропусков все виды правильных трехчленных силогизмов, а его ученик Аристоксен из Тарента перечислил разнообразные комбинации долгих и кратких слогов в стихотворных размерах. Математик Папп (IV в. Н.э.) рассматривал число пар и троек, которые можно получить из трех элементов.
Наверное, у греческих ученых были какие-то неизвестные нам, правила комбинаторных рассчетов, которые скорее всего были неверными. Схоласт Раймонд Люлли создал в ХVIII ст. машину, которая состояла из нескольких кругов, на которые были нанесены основные предикаты, субъекты, атрибуты и другие понятия схоластической логики. Вращая эти круги, он получал различные совмещения понятий и надеялся получить с их помощью истину.
Комбинаторика в странах Востока
В VIII в. н. э. начался расцвет арабской науки. Арабы перевели много произведений греческих ученых, изучили их, а затем достигли успехов в науке о решении уравнений (само слово «алгебра» - арабского происхождения), теории и практике вычислений. Решая вопрос о нахождении корней любой степени, арабские алгебраисты вывели формулу для степени суммы двух чисел, которая известна под не совсем правильным историческим названием «бином Ньютона». Наверное, именно эту формулу знал поэт и математик Омар Хайям (XI-XII вв. Н.э.).
Работы Паскаля и Ферма дали толчок для рождения двух новых ветвей математической науки - комбинаторики и теории вероятностей. Если до них комбинаторные проблемы затрагивались в общих трудах по астрологии, логике и математике, что в значительной мере считалось математическим развлечением, то уже в 1666 г. Готтфрид Вильгельм Лейбниц публикует «Диссертацию о комбинаторном искусстве», в которой впервые появился термин «комбинаторика». Проекты Лейбница казались невыполнимыми тогдашним математикам, но теперь, после создания ЭВМ, много планов Лейбница начали воплощаться в жизнь, а дискретная математика выросла настолько, что смогла вступить в спор с классическим математическим анализом.
В 1713 г. была опубликована книга «Искусство предположений» Якоба Бернулли, в которой указывались формулы для числа размещений из с n элементов по k, выводились выражение для степенных сумм и т.п. Замечательные достижения в области комбинаторики принадлежат одному из крупнейших математиков XVIII в. Леонарду Эйлеру, швейцарцу, проживший почти всю жизнь в России, где был членом Петербургской академии наук. Основная часть научной работы Эйлера посвящена математическому анализу, в котором он проложил новые пути, создал целый ряд новых областей.
После работ Паскаля и Ферма, Лейбница и Эйлера можно было уже говорить о комбинаторике как об отдельной, самостоятельную ветви математики, тесно связанной с другими областями науки, такими, как теория вероятностей, учение о рядах т.д. В конце XVII в. немецкий ученый Гинденбург и его ученики сделали попытку построить общую теорию комбинаторного анализа. Однако она не имела успеха - в то время еще не было накоплено достаточного количества важных и интересных задач, которые могли бы дать необходимый фундамент для такой теории.
III. Актуализация опорных знаний.
Технология« Продолжите предложение ».
На доске написано задание, учащиеся на выбор учителя подходят и дописывают ответ.
Х={0, 2, 3, 4, 7.} У={2, 4, 7, 9, 14.}
ХпУ =
їиУ =
Х\У =
У\Х =Технология «Мозаика».
На доске изображена схема. Ученик получает выражения на листах, ему нужно составить правило выбора формулы для решения задач по комбинаторике
4. Просмотр проекта «Интересная комбинаторика».
Ориентировочный опорный конспект проекта
Профессор Отто Лиденброк - главный герой романа Жюля Верна «Путешествие к центру земли», в букинистической лавке попал на манускрипт XIII в., написанный руническим письмом. (Руны - письменные знаки, употреблявшиеся в средневековье и, по легенде, были изобретены самим Одином - верховным богом в исландской мифологии). Но заинтересовала Отто записка, оставленная в этой книге ее бывшим владельцем, знаменитым алхимиком XVII в. Анре Сакнуссемом. Сомнений не было: в записке говорилось о каком-то великом открытии. И хотя запись была сделана хорошо известным профессору руническим письмом, однако прочитать его не удалось. Сообщение было зашифровано. Прочитать его можно было лишь двумя способами: либо рассмотреть все варианты размещения 20 рунических знаков, или найти ключ к шифру. Как вы думаете, каким способом Отто Лиденброк прочитал записку?
Его ассистент Аксель подсчитал, что переставлять рунические знаки профессору пришлось бы 2 32 902 008 176 640 000 раз. (В. А. Тадеев «Неформальная математика» Тернополь, 2003).Комбинаторика позволила прочитать и крито-микенское линейное письмо. Первые надежные основы расшифровки этой письменности заложила Алиса Д. Кобер, которая защитила в 1932 г. докторскую диссертацию по математике в Колумбийском университете. Рядом с исследованиями по чистой математике, она много усилий приложила к расшифровке древних письменностей. Изучив знаки критского письма, Алиса установила, что это письмо состоит из складов. Кобер получила координатную сетку, в которой вместо осей координат стояли номера гласных и согласных букв. В этой сети был только один недостаток - никто не знал, какие именно гласные и согласные формируют эту систему координат. Лишь через два года после смерти исследовательницы молодой английский архитектор Майкл Вентрис, расширяя ее координатную сетку, попытался угадать значение некоторых гласных (число гласных меньше числа согласных). Одна из попыток закончилась удачно - текст заговорил на языке, напоминающем греческий. Но это не был классический греческий язык «Илиады» и «Одиссеи», а греческий язык более ранней эпохи. Вентрису помог завершить расшифровку выдающийся знаток раннего греческого языка Чедвик. Используя имена царей и списки географических названий, исследователи расшифровывали один состав за другим. А потом началась быстрая расшифровка - три десятка знаков получили свое значение. Это был полный триумф комбинаторного подхода.
Не только азартные игры побудили математиков к комбинаторным размышлениям. Еще с древних времен дипломаты, практиковали тайную переписку, изобретали все более сложные шифры, а секретные службы других государств пытались эти шифры разгадать. Одним из простейших шифров была «тарабарская грамота», в которой буквы заменялись другими по определенным правилам. Однако такие шифры легко разгадывались по характерным сочетаниям букв. Поэтому стали применять шифры, основанные на комбинаторных методах, например, на разных перестановках букв, замена букв с использованием ключевых слов и т.д. Для кодирования и расшифровки привлекались математики. Еще в конце XVI в. расшифровкой переписки между врагами французского короля Генриха III с испанцами занимался один из создателей современной алгебры Франсуа Виет. А в Англии XVII в. монархические заговорщики удивлялись скорости, с которой Кромвель разгадывал их задумы. Монархисты считали шифры, которыми они пользовались в переписке, нерасшифрованными, и считали, что ключи к ним были выданы кем-то из участников мятежа. И только после падения республики и царствования Карла II они узнали, что все их шифры разгадывал один из лучших английских математиков того времени, профессор Оксфордского университета Уоллис, который имел исключительный комбинаторный талант. Он назвал себя основателем новой науки «криптографии». Шифрами пользовались не только дипломаты и мятежники, но и сами ученые. До 17 в. Почти не существовало научных журналов. Ученые узнавали о достижениях своих коллег из книг или частных писем. Это создавало большие трудности при опубликовании новых результатов - ведь издание книг занимало годы, а написать о своих открытиях в письме было рискованно – кто-нибудь мог присвоить изобретение. Поэтому между учеными часто возникали споры на тему преимуществ. Еще в конце XVII в. шли долгие споры.
В древности Архимеду приходилось хитрить. Когда некоторые александрийские ученые присваивали себе его результаты, описанные в письмах, он писал им еще одно письмо, состоящее из формул для вычислений объемов и площадей различных фигур и тел. Ученые утверждали, что эти формулы им давно известны и ничего нового Архимед им не сообщил. Но тут выяснялось, что все эти формулы неверны. Для того, чтобы обеспечить приоритет и не допустить преждевременной огласки полученных результатов, ученые в краткой форме формулировали суть открытия, а потом переставляли буквы и отправляли письма с переставленными буквами своим коллегам. Такие тексты с переставленными буквами назывались анаграммами. Навыки в разгадке сложных шифров помогли ученым, когда археологи начали находить камни и черепа с тайными знаками. Одним из крупнейших успехов в расшифровке было прочтение французским филологом Жаном Франсуа Шамполем иероглифов, которыми писали египтяне еще до того, как возникла наука у древних греков. Технология «Лото».
На доске лист бумаги с ответами. Учащимся раздают на листах задачи с операциями над, соединениями, которые написаны с одной стороны листа и с элементами рисунка с другой стороны. Решив задачу, ученик наклеивает свой элемент рисунка на место, где написан его ответ. В результате школьники получают полный рисунок, который свидетельствует о правильном решении задачи.
Заданиеа) 
б) 
в) 
г) 
д) 
е) 
Просмотр проекта «Применение комбинаторики».
Ориентировочный опорный конспект проекта
Комбинаторика - важный раздел математики, знание которого необходимо работникам различных специальностей. С комбинаторными задачами приходится иметь дело физикам, химикам, биологам, лингвистам, специалистам по кодам и т.п.. Комбинаторные методы лежат в основе решения многих задач теории вероятностей и ее приложений.
Комбинаторика в биологии
Сложность строения биологических систем, их строгая иерархичность, взаимосоединение отдельных процессов в целом организме делают биологию пригодной для применения комбинаторных методов. Советский биолог А. А. Любищев предполагал даже, что схожесть растений и морозных узоров на окнах не случайна - в обоих случаях проявляются определенные законы комбинирования частей в одно целое. Когда биологи начали изучать передачу генетической информации у бактерий, то заметили, что в процессе этой передачи хромосомы переходят от одной бактерии к другой не полностью. Они надеялись, изучая части которые перешли из одной бактерии к другой, определить порядок размещения генов в хромосоме. Но карты хромосом, составленные в разных лабораториях, были непохожимы друг на друга. Однако, детально сравнив полученные карты, французские ученые
Жакоб и Вальмон заметили их комбинаторное сходство. Оказалось, что все эти карты были частями одного кольца - хромосомы бактерий оказывались свернутыми в кольца, которые перед переходом в другую бактерию разрываются, после чего к одному концу прикрепляется фактор, который перетягивает хромосому из одной бактерии к другой. А так как разорваться кольцо могло в любом месте, а фактор мог прикрепиться к любому концу, то и возникало много разных карт, которые запутывали картину.
Одной из наиболее сложных загадок в биологии XX в. было строение «нитей жизни» - молекул белка и нуклеиновых кислот. Оказалось, что молекулы белка - это объединение нескольких длинных цепей, состоявших из 20 аминокислот. Сочетая комбинаторные разбирательства с изучением рентгеновских снимков, ученым удалось разгадать строение многих белков, в том числе гемоглобина, инсулина и т.д. Достижением комбинаторного подхода к проявлениям жизни можно считать расшифровку строения дезоксерибонуклеиновой кислоты (ДНК), сделанную в Кембридже Ф. Криком и Дж. Уотсоном в 1953 г.
Комбинаторика в химии
17 февраля 1869 из хаоса химических элементов, каждый из которых имел свои свойства, возникла таблица - был открыт периодический закон. Это открытие было сделано Дмитрием Ивановичем Менделеевым, профессором Петербургского университета. Готовя курс лекций по общей химии, он задумался над порядком, в котором нужно было рассказывать об элементах. Как писал впоследствии сам ученый, «искать что-то, хотя бы грибы, или какую-то зависимость, можно, как смотря и пробуя». Для того, чтобы «смотреть и пробовать», он начал подбирать, написав на отдельных карточках, названия элементов с их атомными массами и свойствами данного элемента, похожие элементы и атомные массы. Раскладывая свой химический пасьянс, великий ученый после напряженных раздумий нашел правильное размещение элементов. Говорят, что конечный вид таблицы предстал перед ним во сне, когда, утомленный непрерывной работой над ней, он прилег отдохнуть. Поражает, что открытие было сделано Менделеевым за один день - утром 17 февраля 1869 он еще и не начинал раскладывать свой пасьянс, а к вечеру того же дня таблица была готова.
В физике комбинаторика является необходимой при изучении особенностей кристаллов, описания модели ферромагнетизма т.д..
Комбинаторика эпохи компьютеров
В нашу эпоху комбинаторика из области, которая интересовала прежде всего лишь отдельных авторов задач и находила применение в кодировке и расшифровке древних письменностей, превратилась в область, находящуюся на магистральном пути развития науки. Шифрование, кодирование, дешифрование письменной информации - важное, но не единственное применение комбинаторики. Кодами являются также государственные номерные знаки, штрих-коды. Целенаправленный выбор «разных возможных вариантов» необходим для составления расписания движения транспорта, расписания занятий в школе, а еще как аппарат для решения задач теории вероятности.
Проверка умений и навыков решения решать задачи по данной теме.
Самостоятельная работа (5 мин).
Учитель раздает задачи на листах. 1 вариант - ученик выбирает и решает только задачу на размещение, 2 вариант - ученик выбирает и решает только задачу на комбинацию.
1 вариант
1. В группе есть 10 человек. Сколькими способами можно выбрать 5 из них для экскурсии?
2. Сколькими способами можно выбрать старосту и заместителя, если в классе 25 учеников?
3. Сколькими способами можно построить шеренгу из 5 человек.
2 вариант
1. Сколькими способами можно расставить 6 стульев вокруг стола?
2. Сколькими способами можно выбрать инструктора и старшего инструктора из 30 человек?
3. Сколькими способами можно выбрать 2 дежурных из 25 человекч. 1 ч. 2
ansya.ru
Оглавление
Введение
стр. 2
1.
Понятие комбинаторики.
стр. 4
2.
История развития комбинаторики.
стр. 5
2.1
Дерево возможных вариантов
стр. 6
2.2
Перестановки.
стр. 9
2.3
Размещение.
стр. 10
3.
Комбинаторика в различных областях жизнедеятельности человека.
стр. 13
3.1
Комбинаторика в литературе
стр. 13
3.2
Комбинаторика на шахматной доске и в играх
стр. 15
3.3
Комбинаторика и кубик Рубика
стр. 16
3.4
Старинные задачи
стр. 17
Заключение
стр. 18
Литература
стр. 19
Приложение
стр. 21
В практической деятельности человеку часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия. С комбинаторными вычислениями приходится иметь дело представителям многих специальностей: прорабу при распределении между рабочими различных видов работ, диспетчеру при составлении графика движения. Завуч школы, составляя расписание учебных занятий, использует разные комбинации, шахматист из различных комбинаций выбирает наилучшую и т.д.
Современная жизнь делает задачи на комбинаторные вычисления актуальными, так как появление компьютеров резко увеличило возможности комбинаторики и расширило сферу ее применения.
Прикладное значение этой темы очень велико и затрагивает финансовую, демографическую, экологическую, социологическую и другие стороны нашей жизни. Интерес к теме возник, когда я участвовала в олимпиаде по математике, и там встречались следующие задачи:
Задача 1. Из 100 туристов, отправляющихся в заграничное путешествие, немецким языком владеют 30 человек, английским - 28, французским - 42. Английским и немецким одновременно владеют 8 человек, английским и французским - 10, немецким и французским - 5, всеми тремя языками - 3. Сколько, туристов не владеют ни одним языком?
Задача 2. Бег с препятствиями
На дорожках стадиона расставлены барьеры (число барьеров на каждой дорожке указано на рисунке). Кенгуру хочет пробежать от старта до финиша, перепрыгивая через наименьшее возможное число барьеров. Сколько раз Кенгуру придется перепрыгнуть через барьеры?
(A)11; (B) 8; (C) 10; (D) 18; (E) 6;
После олимпиады, я задал учителю математики вопрос: «Как можно удобным способом решить задачи такого типа?» И, после этого узнал, что есть раздел математики - «Комбинаторика».
Зная комбинаторику, мы сможем найти ответы на многие интересные вопросы: сколько существует трёхзначных чисел, сколькими способами в футбольной команде можно выбрать капитана и его заместителя, сколькими способами 8 человек могут встать в очередь к театральной кассе, сколько существует семи значных чисел, не содержащих цифры 5 и, наконец, какова вероятность выиграть в русское лото. Очень интересно! Неужели и я - смогу это понять?
Так появился этот проект. Желание ответить на эти вопросы и определило цель моего проекта.
Цель проекта: научиться решать задачи из раздела «комбинаторика».
Для достижения цели были поставлены следующие задачи:
Изучить исторический и теоретический материал о комбинаторике.
Систематизировать задачи на комбинаторику по типам решения.
Выяснить, какие задачи в жизни приходится решать людям.
При работе над проектом применялись следующие теоретические методы:
-изучение и анализ источников информации по комбинаторике и занимательной математике;
- моделирование приемов использования комбинаторики в задачах.
Понятие комбинаторика.
В обыденной жизни нам нередко встречаются задачи, которые имеют несколько различных вариантов решения. Чтобы сделать правильный выбор, важно не упустить ни один из них. Для этого надо уметь осуществлять перебор всех возможных вариантов или подсчитывать их число. Задачи, требующие такого решения, называются комбинаторными. Область математики, в которой изучают комбинаторные задачи, называется комбинаторикой.
В Энциклопедическом словаре юного математика дано определение: «Комбинаторика — это раздел математики, в котором изучают, сколько комбинаций, подчинённых тем или иным условиям, можно составить из данных объектов»[1]. Комбинаторика нужна для изучения раздела математики «Теория вероятностей», который будет являться обязательным при изучении школьного курса математики.
Способ рассуждений, которым пользуются при решении задачи, называют перебором возможных вариантов.
Раздел 2.
2.1. История развития комбинаторики
С задачами, получившими название комбинаторных, оказывается, люди сталкивались в глубокой древности. Уже несколько тысячелетий назад в Древнем Китае увлеклись составлением магических квадратов, в которых заданные числа располагались так, что их сумма по всем горизонталям, вертикалям и главным диагоналям была одной и той же.
В Древней Греции подсчитывали число различных комбинаций длинных и коротких слов в стихотворных размерах, занимались теорией фигурных чисел, изучали фигуры, которые можно составить из частей особым образом разрезанного квадрата и т.д. Комбинаторные задачи возникли и в связи с такими играми, как шашки, шахматы, домино, карты, кости и т.д.
Первым рассматривал комбинаторику как самостоятельную ветвь науки всемирно известный немецкий учёный Готфрид Вильгельм Лейбниц.
В 1666 году Лейбниц опубликовал «Рассуждения о комбинаторном искусстве». В своём сочинении Лейбниц, вводя специальные символы, термины , находит все k -сочетания из n элементов, выводит свойства сочетаний, строит таблицы сочетаний, после чего рассуждает о приложениях комбинаторики к логике, арифметике, к проблемам стихосложения и др. Мечтой Лейбница, оставшейся неосуществлённой, оставалось построение общей комбинаторной теории.
В XVIII веке к решению комбинаторных задач обращались выдающиеся математики. Замечательные достижения в области комбинаторики принадлежат Леонарду Эйлеру. Он рассматривал задачи о разбиении чисел, о циклических расстановках, о построении магических и латинских квадратов. В 1713 году было опубликовано сочинение Я. Бернулли, в котором с достаточной полнотой были изложены известные к тому времени комбинаторные факты. Комбинаторными задачами интересовались и математики, занимавшиеся составлением и разгадыванием шифров, изучением древних письменностей. Теперь комбинаторика находит приложения во многих областях науки: в биологии, где она применяется для изучения состава белков и ДНК, в химии, механике сложных сооружений и т.д. Комбинаторные задачи физики, химии, биологии, экономики и других наук, которые не поддавались ранее решению из-за трудоемкости вычислений, стали успешно решаться на ЭВМ. В результате этого комбинаторные методы исследования все глубже проникают во многие разделы науки и техники. В частности, с помощью ЭВМ решена проблема четырех красок: доказано, что любую карту можно раскрасить в четыре цвета так, чтобы никакие две страны, имеющие общую границу, не были окрашены в один и тот же цвет.
Еще в 1844 году Дж. Сильвестр говорил: "Число, положение и комбинация - три взаимно пересекающиеся, но различные сферы мысли, к которым можно отнести все математические идеи".
2.2. Дерево возможных вариантов.
Самые разные комбинаторные задачи решаются с помощью составления специальных схем. Внешне такая схема напоминает дерево, отсюда и название метода - дерево возможных вариантов. Ветви дерева отображают различные события, которые могут иметь место. Корень дерева – состояние, в котором возникает необходимость выбора.
Задача 1. Какие трехзначные числа можно составить из цифр 0, 2, 4?
Решение. Построим дерево возможных вариантов, учитывая, что 0 не может быть первой цифрой в числе.
Ответ: 200, 202, 204, 220, 222, 224, 240, 242, 244, 400, 402, 404, 420, 422, 424, 440, 442, 444.
Задача 2. Школьные туристы решили совершить путешествие к горному озеру. Первый этап пути можно преодолеть на поезде или автобусе. Второй этап - на байдарках, велосипедах или пешком. И третий этап пути - пешком или с помощью канатной дороги. Какие возможные варианты путешествия есть у школьных туристов?
Решение. Построим дерево возможных вариантов, обозначив путешествие на поезде П, на автобусе - А, на байдарках - Б, велосипедах - В, пешком - Х, на канатной дороге - К.
Ответ: На рисунке перечислены все 12 возможных вариантов путешествия школьных туристов.
Задача 3. Запишите все возможные варианты расписания пяти уроков на день из предметов: математика, русский язык, история, английский язык, физкультура, причем математика должна быть вторым уроком.
Решение. Построим дерево возможных вариантов, обозначив М - математика, Р - русский язык, И - история, А - английский язык, Ф - физкультура.
Ответ: Всего 24 возможных варианта.
Задача 4.
Саша ходит в школу в брюках или джинсах, к ним надевает рубашки серого, голубого, зеленого цвета или в клетку, а в качестве сменной обуви берет туфли или кроссовки.
а) Сколько дней Саша сможет выглядеть по-новому?
б) Сколько дней при этом он будет ходить в кроссовках?
в) Сколько дней он будет ходить в рубашке в клетку и джинсах?
Решение. Построим дерево возможных вариантов, обозначив Б - брюки, Д - джинсы, С - серая рубашка, Г - голубая рубашка, З - зеленая рубашка, Р - рубашка в клетку, Т - туфли, К - кроссовки.
Ответ: а) 16 дней; б) 8 дней; в) 2 дня.
2.3. Перестановки.
Простейшими комбинациями, которые можно составить из элементов конечного множества являются перестановки.
Д
ва элемента a и b могут быть выписаны в строчку всего двумя способами: ab и ba. Для трёх элементов, существует 6 вариантов. Посчитаем и число перестановок для 4 элементов:
1234, 1243, 1324, 1342, 1423, 1432,
2134, 2143, 2314, 2341, 2413, 2431,
3124, 3142, 3214, 3241, 3412, 3421,
4123, 4132, 4213, 4231, 4312, 4321.
Всего 24 перестановки, расположенные в 4 столбца по 6 перестановок в каждом.
Для числа перестановок n элементов есть обозначение: n! (читаем: «эн факториал»).
Факториал равен произведению всех натуральных чисел от n до 1.
Например, 4! = 1 · 2 · 3 · 4= 24. Здорово! Одна строчка, а перебирая все возможные случаи выше, сколько записи всех перестановок. А если бы было не 4 элемента, а 8? Значит, и не надо было выписывать все возможные перестановки. Неужели так просто. Вот задачи, которые я смог решить.
Задача 1. В семье – 6 человек, и за столом в кухне стоят 6 стульев. Семья решила каждый вечер, ужиная, рассаживаться на эти стулья по-новому. Сколько дней члены семьи смогут осуществлять задуманное?
Решение. Ответ оказывается неожиданно большим: получается почти два года! Объясню его.
Для удобства рассуждений , будем считать, что семья (бабушка, дедушка, мама, папа, дочь, сын) будет рассаживаться на стулья поочередно. Меня интересует, сколько всего существует различных способов их размещения на стульях. Предположим, что первой усаживается бабушка. У нее имеется 6 вариантов выбора стула. Вторым садится дедушка и независимо выбирает стул из 5оставшихся. Мама делает свой выбор третьей, и выбор у нее будет из 4 стульев. У папы будет уже три варианта, у дочки – 2, ну а сын сядет на единственный незанятый стул. По правилу умножения получаем, что имеется 720 различных способов размещения. Таким образом, в «игру с рассаживаниями» семья может играть 720 дней, т.е. почти два года. [3] Теперь стало понятно, что в обеих задачах речь шла о пяти перестановках.
Задача 2. Из группы теннисистов, в которую входят четыре человека – Антонов, Григорьев, Сергеев и Федоров, тренер выделяет пару для участия в соревнованиях. Сколько существует вариантов выбора такой пары?
Решение: Составим сначала все пары, в которые входит Антонов (для краткости будем писать первые буквы фамилий).
Получим три пары: АГ, АС, АФ.
Выпишем теперь пары, в которые входит Григорьев, но не входит Антонов. Таких пар две: ГС, ГФ.
Далее составим пары, в которые входит Сергеев, но не входят Антонов и Григорьев. Такая пара только одна: СФ.
Других вариантов составления пар нет, так как все пары, в которые входит Федоров, уже составлены.
Итак, мы получили 6 пар:
АГ, АС, АФ
ГС, ГФ
СФ,
т.е. 3•2•1=6. значит,
существует всего шесть вариантов выбора тренером пары теннисистов из группы.
2.4. Размещение
Следующее важное понятие комбинаторики — размещение.
Размещением называется расположение «предметов» (объектов) на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны.
Задача 1. В кафе предлагают два первых блюда: борщ, рассольник – и четыре вторых блюда: гуляш, котлеты, сосиски, пельмени. Укажите все обеды из двух блюд, которые может заказать посетитель.
Решение:
Борщ
Рассольник
гуляш
котлеты
сосиски
пельмени
гуляш
котлеты
сосиски
пельмени
Ответ: 8 обедов.
Задача 2. В классе, в котором 25 учеников, нужно выбрать командира, его заместителя и помощника заместителя. Сколькими способами это можно сделать?
Решение:
25 способами можно выбрать любого ученика в командиры.
Затем из 24 оставшихся — заместителя старосты.
После этого любой из 23 оставшихся может оказаться помощником заместителя.
Всего имеем: 25·24·23 = 13800
Ответ: 13800 способов.
Задача 3. В футбольной команде (11 человек) нужно выбрать капитана и вратаря. Сколькими способами это можно сделать?
Решение:
1. Капитаном может стать любой из 11 футболистов.
2. После выбора капитана на роль вратаря могут претендовать 10 оставшихся человек.
Таким образом, есть 11 · 10 = 110 разных вариантов выбора.
Ответ: 110 способов.
Задача 4. Сколько семизначных чисел не содержат цифры 2?
Решение:
Всего цифр 10. Первую цифру не может быть нулем и двойкой, значит её можно выбрать 8 способами. Каждую следующую цифру можно выбрать 9 способами.
8 · 9 · 9 · 9 · 9 · 9 · 9 = 4 251 528.
Ответ. 4 251 528 семизначных чисел.
Вот это количество. А если бы не знать этот способ решения, перебрать все возможные случаи, кажется, невозможно. Это долго и опасно ошибиться.
Задача 5. Сколькими способами можно составить расписание на день из 5 различных уроков, если изучается 14 предметов.
Решение:
В данном примере из 14 предметов нужно выбрать 5. Число способов составления расписания можно посчитать по формуле:
14 · 13 · 12 · 11 · 10 = 240240
Ответ: 240240 способов.
Задача 6. Сколько времени потребуется, чтобы открыть дверь с кодовым замком, если на один набор чисел из 3-х цифр уходит 3 секунды. (Причем порядок нажатия кнопок с числами неважен).
Решение: Первую цифру кода можно выбрать одной из 10 - всего 10 вариантов. Вторую цифру можно выбрать любой из 9 оставшихся. Значит, всего 10*9*8 = 720 комбинаций. Решение было бы верно, если бы не замечание в задаче: Причем порядок нажатия кнопок с числами неважен. Это означает, что композиция 123, 321, 213, и т.п. (всего их 6) одинаковые.
Поэтому надо брать не размещение, а сочетания. Для сочетаний – результат нужно разделить на 6, т.е. на число перестановок из трёх элементов, равных 3!.
720 : 6=120 комбинаций, 120 · 3 = 360 секунд = 6 минут и код будет разгадан.
Ответ: 6 минут.
3. Комбинаторика в различных областях жизнедеятельности человека.
Области применения комбинаторики:
учебные заведения (составление расписаний)
сфера общественного питания (составление меню)
лингвистика (рассмотрение вариантов комбинаций букв)
география (раскраска карт)
спортивные соревнования (расчёт количества игр между участниками)
производство (распределение нескольких видов работ между рабочими)
агротехника (размещение посевов на нескольких полях)
азартные игры (подсчёт частоты выигрышей)
химия (анализ возможных связей между химическими элементами)
экономика (анализ вариантов купли-продажи акций)
криптография (разработка методов шифрования)
доставка почты (рассмотрение вариантов пересылки)
биология (расшифровка кода ДНК)
военное дело (расположение подразделений)
астрология (анализ расположения планет и созвездий)
3.1 Комбинаторика в литературе.
В басне Ивана Андреевича Крылова «Квартет»: «проказница Мартышка, Осёл, Козёл да косолапый Мишка» устроили любопытный эксперимент, они исследовали влияние взаимного расположения музыкантов на качество исполнения.
Проказница-Мартышка, Осёл, Козёл, да косолапый Мишка
Затеяли сыграть Квартет.
Достали нот, баса, альта, две скрипки
И сели на лужок под липки — пленять своим искусством свет.
Ударили в смычки, дерут, а толку нет.
«Стой, братцы, стой! — кричит Мартышка. — Погодите!
Как музыке идти? Ведь вы не так сидите.
Ты с басом, Мишенька, садись против альта,
Я, прима, сяду против вторы;
Тогда пойдёт уж музыка не та: у нас запляшут лес и горы!»
Расселись, начали Квартет;
Он всё-таки на лад нейдёт.
«Постойте ж, я сыскал секрет, —
Кричит Осёл: — мы, верно, уж поладим, коль рядом сядем».
Послушались Осла: уселись чинно в ряд;
А всё-таки Квартет нейдёт на лад.
Вот пуще прежнего пошли у них разборы
И споры, кому и как сидеть.
Случилось Соловью на шум их прилететь.
Тут с просьбой все к нему, чтоб их решить сомненье:
«Пожалуй, — говорят: — возьми на час терпенье,
Чтобы Квартет в порядок наш привесть:
И ноты есть у нас, и инструменты есть;
Скажи лишь, как нам сесть!» —
«Чтоб музыкантом быть, так надобно уменье
И уши ваших, понежней, —
Им отвечает Соловей: —
А вы, друзья, как ни садитесь,
Всё в музыканты не годитесь».
Мартышка, Осёл, Козёл и Мишка пересаживались, считая, что от этого зависит звучание музыки. И если бы не вмешался Соловей, участники квартета, наверное, перепробовали бы все возможные варианты.
Так сколько же существует способов, чтобы рассадить, например в один ряд, четырех музыкантов?
Число перестановок можно посчитать по формуле: 4 3 2 1 = 24 способа.
Ответ: 24 способа.
3.2 Комбинаторика на шахматной доске и в играх.
Шахматы не только популярная игра, но и источник множества интересных комбинаторных задач. Не случайно шахматные термины можно встретить в литературе по комбинаторике. Рассмотрим примеры задач на шахматной доске.
Задача 1: Обойти конем все поля доски, посетив каждое из них по одному разу.
Этой задачей занимались многие математики XVIII и XIX вв., в том числе и Л. Эйлер. Хотя задача была известна и до Эйлера, лишь он впервые обратил внимание на ее математическую сущность. Доказано, что таких маршрутов не более 30 млн. Задачи о маршрутах составлены и для других фигур.
Задача 2: Сколькими способами можно расставить на доске восемь ферзей так, чтобы они не угрожали друг другу, т. е. никакие два из них не стояли бы на одной линии ( вертикали, горизонтали, диагонали).
Доказано, что существует 92 требуемых расстановки. Подобные задачи ставятся для всех шахматных фигур. Исследование конкретных позиций или их классов в игре применяется для достижения определенных результатов, например матовой позиции за определенное число ходов. Так как борьба за уменьшение времени на «обдумывание» хода всей программой является принципиальным фактором, то математики затрачивают массу усилий на создание входящих в нее приложений (задач, решаемых при поиске нужного хода), работающих наиболее быстро, а также требующих по минимуму оперативной памяти. Это направление породило множество изящных логико-вычислительных проблем. Некоторые из них и по сей день предлагаются на различных математических и программистских олимпиадах, а также для развлечения на досуге.
Выдающиеся шахматисты Клод Шеннон и Михаил Ботвинник внесли огромный вклад в создание математической модели шахматной игры и способствовали прогрессу в интеллектуализации программ для нее.
Компьютерные шахматы — едва ли не самый убедительный пример за полвека развития информационных технологий, когда именно в интеллектуальной деятельности автомат успешно соперничает с человеком.
3.3 Комбинаторика и кубик Рубика.
Необыкновенно популярной головоломкой стал кубик Рубика, изобретенный в 1975 году преподавателем архитектуры из Будапешта Эрне Рубиком для развития пространственного воображения у студентов.
Кубик Рубика – это куб, как бы разрезанный на 27 одинаковых кубиков. В исходном положении каждая грань куба окрашена в один из 6 цветов. Остроумный механизм позволяет поворачивать любой слой из 9 кубиков, примыкающий к одной грани куба, вокруг ее центра. При этом цвета граней смешиваются. Задача состоит в том, чтобы вернуть разноцветные грани кубика в исходное положение. Теоретически из любого состояния кубика можно вернуться в исходное, не более чем за 23 хода. Лучшее время, показанное на чемпионате мира 1982 г. по скоростной сборке кубика Рубика, составило всего 22,95 секунды.
Кубик Рубика служит не только развлечением, но и прекрасным наглядным пособием по комбинаторике.
3.4 Старинные задачи
Задача: «Волк, козел и капуста»
Крестьянину нужно перевезти через реку волка, козла и капусту. Лодка так мала, что в ней кроме крестьянина может поместиться только или волк, или козел, или капуста. Но если оставить волка с козлом, он его съест, а если оставить козла с капустой, то будет съедена капуста. Как быть крестьянину?
Для решения требуется путем взаимной перестановки элементов расположить их в соответствии с условием задачи в определенном порядке. В случае с крестьянином переправу следует начать с перевозки козла. Затем крестьянин возвращается и берет волка, которого перевозит на другой берег и оставляет там, а козла возвращает назад на предыдущий берег. Оттуда забирает капусту и перевозит ее к волку. А затем возвращается и забирает козла.
Задача-игра: «Крестики-нолики»
Самая известная древняя игра. В квадрате, разделенном на девять клеток, игроки по очереди ставят в свободную клетку свой знак: крестик или нолик, стараясь выстроить три крестика или три нолика подряд. Тот, кто первым сделает это, тот и выигрывает.
Если не делать ошибок, то игра оканчивается в ничью. Выиграть можно только в том случае, если противник ошибется. Самый правильный ход –
занять угловую клетку. И если партнер не ответит на это своим знаком в центре, то он проиграл.
Задача-игра: «Ним» Пусть имеется одна или несколько групп предметов. Играющие берут по очереди предметы из групп по правилам, которые заранее устанавливают: какое количество предметов разрешается брать за один раз и из скольких групп. Существует множество вариантов игры, и для большинства известна наилучшая стратегия, ведущая к выигрышу.
Заключение
В ходе проекта мною рассматривается история возникновения комбинаторики как науки, начиная с Древнего Китая и Древней Греции и заканчивая современным периодом ее развития. В работе приводятся сведения о великих математиках, которые стояли у истоков теории комбинаторных задач таких, как П. Ферма, Галилео Галилей, Я. Бернулли, Паскаль, Лейбниц, Л. Эйлер и многие другие.
Таким образом, изложенные сведения, доказывают, что комбинаторные задачи сопровождают человечество на протяжении всей истории, переплетаясь с искусством и наукой, что математике присущ элемент игры, которая тренирует интеллект и развивает самые различные способности, особенно творческие.
В рамках проекта полученная информация была изучена и применена при решении задач на перестановки, размещения, и были сделаны выводы, что несомненно, знание правил решения комбинаторных задач дает шанс намного быстрее прийти к положительному результату в логических рассуждениях.
В ближайшем будущем я научусь решать более сложные задачи комбинаторики, а знания по этой теме будут востребованы при решении задач олимпиадного типа и помогут мне в будущем при подготовке к итоговой аттестации по математике.
Вывод: Комбинаторика повсюду. Комбинаторика везде. Комбинаторика вокруг нас. Думаю, что цели я добился, так как после написания работы расширил и углубил свои знания по комбинаторике и научился решать задачи из этого раздела.
Литература:
1.Энциклопедический словарь юного математика - /составитель Савинов А.П..- М.: Педагогика » -1985г.-352стр с ил.
2.Виленкин Н.Я. Комбинаторика.: Изд. « Наука»,1969г.
3.Деплан И. Я ., Виленкин Н.Я. За страницами учебника математики.- Пособие для учащихся 5-6кл средних школ. М.:Просвещение,1989-287стр. с иллюстрациями.
4.Г. Я. Гик «Занимательные математические игры». - М.:Знание,1982г.
5.Математическая энциклопедия /Виноградов И.М..-М.:Советская энциклопедия. Том 3.,1984г
6.Богомолов Н.В. Практические занятия по математике: Учеб. Пособие для техникумов. – 2-е изд., перераб.-М.: Высш. Школа, 1983.-399 с., ил.
7.Энциклопедия для детей. Т.11. Математика/Глав. Ред. М.Д. Аксенова.- М.: Аванта+, 2002.- 688с.: ил.
8/
Раздел 5.
Приложение
Задача. У меня есть любимый костюм, в котором я хожу в школу. Я надеваю к нему белую, голубую, розовую или красную блузку. Кроме того у
Летом на каникулах наша семья планирует поездку в отпуск в г. Тюмень.
Сколько существует вариантов маршрутов из г. Белоярский до г. Тюмени
и какой из них выгодней по времени и стоимости?
infourok.ru
Комбинаторика — раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.
Выбором объектов и расположением их в том или ином порядке приходится заниматься чуть ли не во всех областях человеческой деятельности, например конструктору, разрабатывающему новую модель механизма, ученому-агроному, планирующему распределение сельскохозяйственных культур на нескольких полях, химику, изучающему строение органических молекул, имеющих данный атомный состав.
С аналогичными задачами, получившими название комбинаторных, люди столкнулись в глубокой древности. Уже несколько тысячелетий назад в Древнем Китае увлекались составлением магических квадратов (см. Магические и латинские квадраты), в которых заданные числа располагали так, что их сумма по всем горизонталям, вертикалям и главным диагоналям была одной и той же. В Древней Греции подсчитывали число различных комбинаций длинных и коротких слогов в стихотворных размерах, занимались теорией фигурных чисел, изучали фигуры, которые можно составить из частей особым образом разрезанного квадрата, и т. д.
Комбинаторные задачи возникали и в связи с такими играми, как шашки, шахматы, домино, карты, кости и т. д. (Например, задача о расстановке восьми ферзей на шахматной доске так, чтобы ни один из них не оказался под боем, об обходе всех полей доски шахматным конем и т. д. (см. Математика на шахматной доске).
Комбинаторика становится наукой лишь в XVII в. — в период, когда возникла теория вероятностей. Чтобы решать теоретико-вероятностные задачи, нужно было уметь подсчитывать число различных комбинаций, подчиненных тем или иным условиям. После первых работ, выполненных в XVI в. итальянскими учеными Дж. Кардано, Н. Тартальей и Г. Галилеем, такие задачи изучали французские математики Б. Паскаль и П. Ферма. Первым рассматривал комбинаторику как самостоятельную ветвь науки немецкий философ и математик Г. Лейбниц, опубликовавший в 1666 г. работу «Об искусстве комбинаторики», в которой впервые появляется сам термин «комбинаторный». Замечательные достижения в области комбинаторики принадлежат Л. Эйлеру. Комбинаторными задачами интересовались и математики, занимавшиеся составлением и разгадыванием шифров, изучением древних письменностей. Теперь комбинаторика находит приложения во многих областях науки: в биологии, где она применяется для изучения состава белков и ДНК, в химии, механике сложных сооружений и т. д.
По мере развития комбинаторики выяснилось, что, несмотря на внешнее различие изучаемых ею вопросов, многие из них имеют одно и то же математическое содержание и сводятся к задачам о конечных множествах и их подмножествах. Постепенно выявилось несколько основных типов задач, к которым сводится большинство комбинаторных проблем. Важную область комбинаторики составляет теория перечислений. С её помощью можно подсчитать число решений различных комбинаторных задач. В основе этой теории лежат «правило суммы» и «правило произведения». Они гласят: «если множество $A$ состоит из $m$ элементов, а множество $B$ — из $n$ элементов, причем эти множества не имеют общих элементов, то их объединение $A⋃B$, т. е. совокупность всех элементов из $A$ и $B$, содержит $m+n$ элементов; множество $A×B$, состоящее из всевозможных пар $(a,b)$, где элемент $a$ принадлежит множеству $A$, а элемент $b$ принадлежит множеству $B$, содержит $mn$ элементов».
С помощью правила суммы легко сосчитать и число элементов в $A⋃B$, когда $A$ и $B$ имеют общие элементы. Если обозначить через $A⋂B$ множество всех общих элементов у множеств $A$ и $B$, то оно равно $n(A)+n(B)−n(A⋂B)$, где $n(A)$ — число элементов в множестве $A$. Это утверждение — частный случай так называемой формулы перекрытий.
Часто приходится считать число последовательностей длины $m$, составленных из элементов некоторого множества $A$, состоящего из $n$ элементов, как в случае, когда среди элементов последовательности могут быть повторяющиеся, так и в случае, когда все эти элементы должны быть различными. В первом случае последовательности называют размещениями с повторениями из $n$ элементов по $m$ и их число обозначают $\bar{A}_{n}^{m}$, а во втором — размещениями без повторений, их число обозначают $A_{n}^{m}$. Формулы для $\bar{A}_{n}^{m}$ и $A_{n}^{m}$ таковы:
$\bar{A}_{n}^{m}={{n}^{m}},$ $A_{n}^{m}=n(n−1)\cdot \ldots \cdot (n−m+1).$
Рассмотрим различные размещения без повторений из $n$ элементов по $n$, очевидно, что они отличаются друг от друга лишь порядком элементов; их называют перестановками из $n$ элементов. Число ${{P}_{n}}$ таких перестановок равно $n!$ (см. Факториал):
${{P}_{n}}=A_{n}^{n}=n!.$
Если отвлечься от порядка элементов, то возникает задача: сколько подмножеств, содержащих $m$ элементов и отличающихся одно от другого хотя бы одним элементом, можно извлечь из множества $A$, содержащего $n$ элементов. В комбинаторике такие подмножества называют сочетаниями из $n$ элементов по $m$, их число обозначают $C_{n}^{m}$. Можно доказать, что
$C_{n}^{m}=\frac{n!}{m!\left( n-m \right)!}.$
Целый ряд комбинаторных задач возникает при разбиении множеств на части: найти число таких разбиений, если число частей равно $k$; найти, сколькими способами можно число $n$ записать в виде суммы $k$ слагаемых; найти, сколькими способами можно разложить $n$ предметов по $k$ ящикам, и т. д. Обычно задачи теории разбиений и раскладок сводятся к формуле перекрытий и разобранным выше основным задачам комбинаторики. Такими же способами решаются комбинаторные задачи с ограничениями, например подсчет числа размещений с повторениями, в которых ни один элемент не стоит два раза подряд, и т. д.
В решении комбинаторных задач часто используют графические методы — изображение разбиений числа на слагаемые в виде точечных диаграмм, так называемые графы (геометрические фигуры, состоящие из точек и соединяющих их отрезков) и т. д. Теория графов стала в наши дни одной из наиболее бурно развивающихся частей комбинаторики. Многие общие теоремы этого раздела математики формулируются на языке графов.
Комбинаторика не сводится только к подсчету количества тех или иных подмножеств или последовательностей. При решении комбинаторных проблем иногда нужно лишь доказать, что данная проблема имеет решение, или убедиться в отсутствии его. Например, доказано следующее утверждение: для любых чисел $m$ и $n$ найдется такое число $N$, что любой граф, состоящий из $N$ точек и всех соединяющих эти точки отрезков (они раскрашены в $m$ цветов), содержит часть, состоящую из $n$ точек и соединяющих их отрезков, такую, что все отрезки имеют один и тот же цвет (теорема Рамсея).
Если заданным условиям удовлетворяют несколько конфигураций, т. е. если комбинаторная задача имеет несколько решений, то может возникнуть вопрос о выборе из них решения, оптимального по тем или иным параметрам. Например, если имеется несколько городов, каждые два из которых соединены авиалинией, то возникает задача о том, как путешественнику побывать по одному разу в каждом городе, налетав наименьшее расстояние.
Комбинаторные задачи физики, химии, биологии, экономики и других наук, которые не поддавались ранее решению из‑за трудоемкости вычислений, стали успешно решаться с использованием компьютеров. В результате этого комбинаторные методы исследования все глубже проникают во многие разделы науки и техники.
В 1970–1980 гг. комбинаторика добилась новых успехов. Например, с помощью компьютера решена проблема четырех красок: доказано, что любую карту можно раскрасить в четыре цвета так, чтобы никакие две страны, имеющие общую границу, не были окрашены в один и тот же цвет.
yunc.org
