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

«Юный исследователь - 2020»

Секция «Математика, физика, информатика»

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

Пензина Дарья Владимировна, СОШ № 6 г. Чебоксары, 6Б класс

Научный руководитель:

Сафронова Ирина Геннадьевна, учитель математики СОШ № 6 г. Чебоксары

Введение

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

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

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

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

Для достижения цели были поставлены задачи:

1. Ознакомиться с  теоретическим материалом по данной проблеме.
2. Применить   полученные теоретические знания  при решении задач.
3. Изучить  наиболее интересные и увлекательные фокусы и занимательные задачи, основанные на методах комбинаторики.

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

В работе были использованы труды  Я.И. Перельмана,  В.С. Лютикаса, М.Б.Гельфанда, В.С. Павловича и других авторов. В ходе исследования также были проведены многочисленные эксперименты по разгадыванию математических фокусов с использованием комбинаторики с участием ребят 6Б класса.

Данная работа  призвана  повысить интерес учащихся к изучению математики.

Глава 1.История комбинаторики

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

Древние времена

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

Историки отмечают также комбинаторные проблемы в руководствах по игре в Го и других играх.

Большой интерес математиков многих стран с древних времен неизменно вызывали магические квадраты. Это квадратные таблицы из целых чисел, в которых сумма во всех столбцах, строках и двух главных диагоналях равна одному и тому же числу. В начальной школе мы сами составляли такие квадраты (3 на 3, 4 на 4).

Магический квадрат- древнекитайского происхождения. Согласно легенде, во времена правления императора Ю (около 2200 г. до н.э.) из вод реки Хуанхэ всплыла священная черепаха, на панцире которой  были начертаны таинственные  иероглифы и эти знаки известны под названием ло-шу и равносильны магическому квадрату. Позже о магических квадратах узнали в Индии, а затем в Японии где в 16 веке магическим квадратам была посвящена обширная литература. Европейцев с магическими квадратами познакомил в 15 веке византийский писатель Мосхопулос.

На рисунке древний и современный магические квадраты.

          Классическая задача комбинаторики: «сколько есть способов извлечь m элементов из N возможных» упоминается еще в сутрах древней Индии – начиная примерно с V века до н.э.  Античные греки также рассматривали отдельные комбинаторные задачи, хотя систематическое изложение ими этих вопросов, если оно конечно существовало, до нас не дошло.

Новое время

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

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

Первые ученые

Термин  «комбинаторика» был введен в математический обиход знаменитым Лейбницем. Готфрид Вильгельм Лейбниц (1.07.1646 – 14.11.1716) – всемирно известный немецкий ученый, занимался философией, математикой, физикой, организовал Берлинскую академию наук и стал ее первым президентом. В математике он вместе с И.Ньютоном разделяет честь создателя дифференциального и интегрального исчисления. В 1666 году Лейбниц опубликовал «Рассуждения о комбинаторном искусстве». В своем сочинении Лейбниц, вводя специальные символы, термины для подмножеств и операций над ними находит все k – сочетания из n элементов, выводит свойства сочетаний, строит таблицы сочетаний, после чего рассуждает о приложениях комбинаторики к логике, арифметике, проблемам стихосложения и др. В течение всей своей жизни Лейбниц многократно возвращался к идеям комбинаторного искусства. Комбинаторику он понимал весьма широко, именно, как составляющую любого исследования, любого творческого акта, предполагающего сначала анализ (расчленение целого на части), а затем синтез (соединение частей в целое). Мечтой Лейбница, оставшейся, увы, неосуществленной, оставалось построение общей комбинаторной теории. Комбинаторике Лейбниц предрекал блестящее будущее, широкое применение.

В XVIII веке к решению комбинаторных задач обращались выдающиеся математики. Так, Леонард Эйлер рассматривал задачи о разбиении чисел, о паросочетаниях, о циклических расстановках, о построении магических латинских квадратов. В 1713 году было опубликовано сочинение Я. Бернулли «Искусство предположений», в котором с достаточной полнотой были изложены известные к тому времени комбинаторные факты. «Искусство предположений» появились после смерти автора, и не было автором завершено.

Для вывода формул автор использовал наиболее простые и наглядные методы, сопровождая их многочисленными таблицами и примерами. Сочинение Я. Бернулли превзошло работы его предшественников и современников систематичностью, простотой методов, строгостью изложения и в течение XVIII века пользовалось известностью не только как серьезного научного трактата, но и как учебно-справочного издания. В работах Я. Бернулли и Лейбница тщательно изучены свойства сочетаний, размещений, перестановок.

Термин «тактика» ввел в математику английский математик Джеймс Джозеф Сильвестр (1814 – 1897) в 1861 году. Сильвестр определял тактику как раздел математики, изучающей расположение элементов друг относительно друга.

Глава 2. Методы решения комбинаторных задач

Перебор возможных вариантов

Простые задачи решают обыкновенным полным перебором возможных вариантов без составления различных таблиц и схем.

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

Ответ: 11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43, 44, 45, 51, 52, 53, 54, 55.

Задача 2. 
В кружок бального танца записались Ваня, Костя, Дима, Олег, Даша, Оля, Нина, Света. Какие танцевальные пары девочки и мальчика могут образоваться?

Ответ:  1) Даша - Ваня, 2) Даша - Костя, 3) Даша - Дима, 4) Даша - Олег, 5) Оля - Ваня, 6) Оля - Костя, 7) Оля - Дима, 8) Оля - Олег, 9) Нина - Ваня, 10) Нина - Коля, 11) Нина - Дима, 12) Нина - Олег, 13) Света - Ваня, 14) Света - Костя, 15) Света - Дима, 16) Света - Олег.

Дерево возможных вариантов

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

Задача 3. Какие трехзначные числа можно составить из цифр 0,2,4? Решение: построим дерево возможных вариантов, учитывая, что 0 не может быть первой цифрой в числе.
 

Ответ: 200, 202, 204, 220, 222, 224, 240, 242, 244, 400, 402, 404, 420, 422, 424, 440, 442, 444.

Задача 4. Запишите все возможные варианты расписания пяти уроков на день из предметов: математика, русский язык, история, английский язык, физкультура, причем математика должна быть вторым уроком.

Решение. Построим дерево возможных вариантов, обозначив М - математика, Р - русский язык, И - история, А - английский язык, Ф - физкультура.

Ответ: Всего 24 возможных варианта:

Составление таблиц

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

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

Решение. Составим таблицу: слева первый столбец - первые цифры искомых чисел, вверху первая строка - вторые цифры.

Ответ : 28

Задача 6. Маша, Оля, Вера, Ира, Андрей, Миша и Игорь готовились стать ведущими на Новогоднем празднике. Назовите возможные варианты, если ведущими могут быть только одна девочка и один мальчик.

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

Правило умножения

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

Задача 7.  В футбольном турнире участвуют несколько команд. Оказалось, что все они для трусов и футболок использовали белый, красный, синий и зеленый цвета, причем были представлены все возможные варианты. Сколько команд участвовали в турнире?

Решение. Трусы могут быть белого, красного, синего или зеленого цвета, т.е. существует 4 варианта. Каждый из этих вариантов имеет 4 варианта цвета майки.

                                          4 х 4 = 16.              Ответ: 16 команд.

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

Решение. Первой в двузначном числе может быть 5 цифр (цифра 0 не может быть первой в числе), второй в двузначном числе может быть 4 цифры (0, 2, 4, 6, т.к. число должно быть четным).             5 х 4 = 20.               Ответ: 20 чисел.

Глава 3. Применение приемов  комбинаторики в фокусах

Фокус первый  

Троим друзьям во время вашего отсутствия предлагается спрятать в карман карандаш, телефон и ластик. На стол ставится тарелка с 24 конфетами. Вы беретесь отгадать -у кого какая вещь.     Процедура  отгадывания проводится так. Возвратившись в комнату после того, как вещи спрятаны, вы начинаете с того, что вручаете участникам конфеты. Одному вы даете 1 конфету, второму-2, третьему – 3.  Затем  снова удаляетесь, оставив друзьям следующую инструкцию - каждый берет себе из тарелки определенное количество конфет:

Обладатель карандаша- столько, сколько ему вручено;

Обладатель телефона- вдвое больше, чем ему дали;

Обладатель ластика – вчетверо больше, чем ему дали, 

прочие конфеты остаются на тарелке. Вернувшись в комнату и посмотрев на оставшиеся конфеты, вы точно определяете у кого какая вещь.

Решение: Вещи обозначим буквами карандаш - к, телефон –т, ластик -л.

Вещи могут распределиться 6 способами

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

Вы видите, что остаток орехов во всех случаях различается. Поэтому, зная остаток, вы легко устанавливаете каково распределение вещей.

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

Фокус второй

Перед зрителями раскладывается 10 пар карт картинками вниз. После этого вы предлагаете одному из зрителей взять любую пару, запомнить карты и положить их обратно. При этом вы отворачиваетесь и не видите, какую пару карт смотрели. Далее вы собираете карты в колоду и, не перетасовывая, раскладываете в 4 ряда по 5 карт картинками вверх. Зрителю предлагается показать, в каком ряду или каких рядах лежат эти 2 карты, что он и делает. После этого вы безошибочно определяете эти  две карты.

Суть фокуса в том, чтобы разложить карты в ряды таким образом, чтобы каждая пара карт имела разное расположение. Если представить данные в виде таблицы, получается такая картина:

Как видим, всего существует 10 комбинаций расположения карт, из них в 4 случаях парные карты располагаются в одном ряду, и в 6 случаях – в разных.  Раскладывая карточные пары, нужно сразу помещать их в нужные позиции. Но сделать это довольно сложно, поэтому был придуман специальный лингвистический код-подсказка, помогающий разложить карты в необходимой последовательности: «наука умеет много гитик».

Н  А  У  К  А

У  М  Е  Е  Т 

М Н  О  Г О

Г   И  Т  И К

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

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

Заключение

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

На сегодняшний день методы комбинаторики могут быть применены во многих сферах нашей жизни:

• производство (распределение нескольких видов работ между рабочими);
•  агротехника (размещение посевов на нескольких полях);
•  учебные заведения (составление расписаний);
•  химия (анализ возможных связей между химическими элементами);
•  лингвистика (рассмотрение вариантов комбинаций букв);
•  азартные игры (подсчёт частоты выигрышей);
•  экономика (анализ вариантов купли-продажи акций);
•  криптография (разработка методов шифрования);
•  сфера общественного питания (составление меню);
•  доставка почты (рассмотрение вариантов пересылки);
•  спортивные соревнования (расчёт количества игр между участниками);
•  биология (расшифровка кода ДНК);
•  военное дело (расположение подразделений);
•  астрология (анализ расположения планет и созвездий);

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

В результате выполнения данной работы мы пришли к следующим выводам:

1. Изучение  комбинаторики представляет огромный интерес у учащихся.
2. Существует множество способов решения комбинаторных задач, каждый из которых применяется для решения определенного типа задач.
3. С помощью методов комбинаторики можно решать и создавать новые занимательные математические задачи и фокусы.
4. Комбинаторика - один из разделов математики, который имеет самое широкое практическое применение во всех отраслях производства и жизни человека.

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

Список литературы

1. Журнал « Математика в школе»

-№ 1- 1999 г ,стр .54;

-№ 4-  2002 г,  стр 59;

2. Библиотека « Первое сентября»

« Я иду на урок математики», 6 класс, М, « Первое сентября», 2001 г.

3. В.С. Лютикас « Школьнику о теории вероятностей», М., « Просвещение», 1983 г.

4. Я.И. Перельман « Живая математика», М,  «Наука», Главная редакция физико- математической литературы, 1978 г.

5. М.Б.Гельфанд, В.С. Павлович « Внеклассная работа по математике», М., « Просвещение», 1965 г.

6. В.А. Гусев, А.И. Орлов « Внеклассная работа по математике в 6-8 классах», М., « Просвещение», 1984 г.

7.  И.Ф. Шарыгин, А.В. Шевкин « Математика. Задачи на смекалку», 5-6 класс, М., « Просвещение», 1995 г.