КОМБИНАТОРИКА. РЕШЕНИЕ ЗАДАЧ С ПОМОЩЬЮ КРУГОВ ЭЙЛЕРА.

II Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке

Личный портфель

КОМБИНАТОРИКА. РЕШЕНИЕ ЗАДАЧ С ПОМОЩЬЮ КРУГОВ ЭЙЛЕРА.

Щербакова А.Ю. 1
1
Коренец Е.И. 1
1
Автор работы награжден дипломом победителя III степени
Диплом школьникаСвидетельство руководителя
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
         

Именно математика дает

надежнейшие правила:

кто им следует – тому не опасен

обман чувств.

Л. Эйлер

Введение

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

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

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

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

Термин «комбинаторика» происходит от латинского слова «combina», что в переводе на русский означает – «сочетать», «соединять».

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

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

Основополагающий вопрос: А все ли я знаю о комбинаторике?

Проблемный вопрос: Может ли помочь комбинаторика в реальной жизни?

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

Задачи:

  • Познакомиться с историей возникновения науки комбинаторики;

  • Находить возможные комбинации для решения комбинаторных задач

  • Уметь составлять и решать задачи с помощью кругов Эйлера;

  • Поработать с ресурсами Internet;

  • Применять полученные знания в дальнейшем обучении;

  • Расширить и углубить представление о практическом значении математики в жизни;

  • Уметь работать с научно-познавательной литературой, анализировать, делать выводы.

Объект исследования : логические задачи.

Методы:отбор источников информации, изучение материала и анализ его.

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

История комбинаторики

Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Комбинаторные мотивы можно заметить в символике китайской «Книги Перемен»(Vвек до н.э.). По мнению её авторов, все в мире комбинируется из различных сочетаний мужского и женского начал, а также восьми стихий: земля, горы, вода, ветер, гроза, огонь, облака и небо. Большой интерес математиков вызывали магические квадраты.(см.Приложение 1) Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э. Индийцы умели вычислять числа, которые сейчас называют «сочетания».Античные греки рассматривали комбинаторные задачи. Хрисипп (IIIв. до н. э.) и Гиппарх(II в.до н.э.) подсчитывали сколько следствий можно получить из 10 аксиом. У Хрисиппа получилось более миллиона. Во все века математики исследовали задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями. Позднее Д.Кардано провел исследование азартной игры в кости . (Азартными называют те игры, в которых выигрыш зависит не только от умения игрока, но и от случайности). Было замечено, что при многократном бросании однородного кубика (все шесть граней которого отмечены соответственно числами 1, 2, 3, 4, 5, 6) число очков от 1 до 6 выпадают в среднем одинаково часто, иными словами, выражаясь языком математики, выпадение определённого числа очков имеет вероятность, равную 1/6. Аналогично вероятность появления на верхней грани кости чётного числа очков равна 3/6, так как из шести равновозможных случаев чётное число появляется только в трёх. Математически заинтересовались азартной игрой П.Ферма и Б.Паскаль. Помимо азартных игр, комбинаторные методы использовались в криптографии - как для разработки шифров, так и их взломов. Комбинаторика и треугольник Паскаля. Паскаль много занимался биномиальными коэффициентами и открыл их способ вычисления. Число сочетаний можно вычислять не через факториал, а с помощью арифметического треугольника. Строится треугольник: его бедра и вершина состоят из единиц, а в основании каждый элемент строки получается суммированием двух стоящих непосредственно над ним элементов.(см.Приложение 2) Паскаль также как и Лейбниц считается основоположником современной комбинаторики .(см.Приложение 3) А вот сам термин комбинаторика придумал Лейбниц. В 1666г. он опубликовал книгу «Рассуждения о комбинаторном искусстве ». Его ученик - Якоб Бернулли (см.Приложение 4) - основатель теории вероятности, изложил много интересного о комбинаторике. Дал научное обоснование теории сочетаний и перестановок. Изучением размещений занимался Я. Бернулли во второй части своей книги «Искусство предугадывания» в 1713 г., в которой указал формулы для числа размещений из n элементов по k, выводились выражения для степенных сумм .

Позднее обнаружили тесную связь между комбинаторными и аналитическими задачами Абрахам де Муавр Джеймс Стирлинг. Они нашли формулы для нахождения факториала. Окончательно комбинаторику, как раздел математики, оформил в своих трудах Эйлер. Кроме перестановок и сочетаний Эйлер изучал разбиение, а также сочетания и размещения с условиями.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • биология (расшифровка кода ДНК)

  • военное дело (расположение подразделений)

  • астрология (анализ расположения планет и созвездий

Теория конфигураций и теория перечисления

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

Правило суммы:

Если элемент A можно выбрать m способами, а элемент B можно выбрать k способами, то выбор элемента A или B можно осуществить m + k способами.

Правило суммы можно перефразировать на теоретико-множественном языке. Обозначим через | A | число элементов множества A, через A B - объединение множеств A и B, через AxB - декартово произведение множеств A и B. Тогда для непересекающихся множеств A и B выполняется равенство:

| A B | = | A | + | B |.

Обобщением правила суммы является правило произведения.

Правило произведения:

Если элемент A можно выбрать m способами, а после каждого выбора элемента A элемент B можно выбрать k способами, тогда, упорядоченную пару элементов (A, B) можно выбрать m*k способами.

Правило произведения можно распространить на выбор последовательности (x1, x2, …, xn) произвольной конечной длиныn. На теоретико-множественном языке правило произведения формулируется так:

| Aх B | = | A | | B |.

Правило размещения.

Назовём множество, содержащееn элементов, n-множеством.

Последовательность (x1, x2, …, xk ) длины k без повторяющихся элементов из элементов данного n-множества назовём k-размещением.

Обозначим символом число размещений из n по k элементов (от фран. "arrangement" - размещение). Используя правило произведения, вычислим число . Пусть произвольное размещение длины k имеет вид: (x1, x2, …, xk ).

Элемент x1 можно выбрать n способами. После каждого выбора x1 элемент x2 можно выбрать (n - 1) способами. После каждого выбора элементов x1 и x2 элемент x3 можно выбрать (n - 2) способами, и т.д. После каждого выбора элементов x1, x2, …, xk-1 элемент xk можно выбрать (n -(k - 1)) = (n - k + 1) способами. Тогда, по правилу произведения, последовательность (x1; x2; , …, xk ) можно выбрать числом способов, равным

n(n - 1)(n - 2) … (n - k + 1) = (1.1)

Произведение в левой части равенства (1.1) умножим и разделим на (n - k)!, получим:

. (1.2)

Если в форуме (1.2) k = n, то есть число Pn перестановок из n элементов

Pn = n! (от "permutation"- перестановка).

Правило сочетания.

k-подмножество данного n-множества называется k-сочетанием.

Обозначим через число k-сочетаний из данныхn элементов. Формулу для числа получим, рассуждая следующим образом. Если каждое сочетание упорядочить всеми возможными способами, то получим все k-последовательностей изn элементов, без повторений, то есть все k-размещения. Иными словами, Откуда: (1.3) или Предполагая, что n и k - целые положительные числа и 0!=1, сформулируем основные свойства сочетаний.

Основные свойства сочетаний.

  1. Условились, что

Как выбрать формулу? (см.Приложение 6) Сводка формул для всех видов соединений. (см.Приложение 7)

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

Пример. В корзине находятся 20 орехов, из которых 7 грецких. Наудачу выбирают 5 орехов. Найти вероятность того, что среди выбранных орехов содержатся 2 грецких.

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

Задачи.

  1. Найти вероятность того, что случайно выбранное 5-значное (десятичное) число не содержит цифры 5.

  2. Предприятие располагает 5 вакансиями для мужчин, 5 вакансиями для женщин и 4 вакансиями для работников любого пола. В отдел кадров предприятия обратилось 20 человек, среди которых 12 мужчин и 8 женщин. Сколькими способами предприятие может заполнить имеющиеся вакансии?

  3. В классе 25 учеников, из которых 13 юношей и 12 девушек. Сколькими способами 25 учеников могут встать в шеренгу так, чтобы юноши после удаления из строя девушек, оказались построенными по росту; аналогично девушки после удаления из строя юношей оказались построенными по росту?

Круги Эйлера

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

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

Автор метода - ученый Леонард Эйлер (1707-1783) (см.Приложение 8) . Он так и говорил о названных его именем схемах: «круги подходят для того, чтобы облегчить наши размышления». Эйлер считается немецким, швейцарским и даже российским математиком, механиком и физиком. Дело в том, что он много лет проработал в Петербургской академии наук и внес существенный вклад в развитие российской науки. Метод Эйлера получил заслуженное признание и популярность. И после него немало ученых использовали его в своей работе, а также видоизменяли на свой лад. Например, чешский математик Бернард Больцано использовал тот же метод, но с прямоугольными схемами. Круги Эйлера имеют прикладное назначение. С их помощью на практике решаются задачи на объединение или пересечение множеств в математике, логике. Круги Эйлера можно разделить их на те, что описывают объединение каких-то понятий и описывают пересечение множеств по какому-то признаку. (см.Приложение9)

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

Чертеж, вроде этого, поможет определиться с выбором:

Рассмотрим несколько примеров задач, которые можно решить с помощью кругов Эйлера.

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» - символ «&».

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети интернет.

Запрос

Найдено страниц (в тысячах)

Крейсер | Линкор

7000

Крейсер

4800

Линкор

4500

Какое количество страниц (в тысячах) будет найдено по запросу Крейсер & Линкор?

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

Решение:

При помощи кругов Эйлера изобразим условия задачи. При этом цифры 1, 2 и 3 используем, чтобы обозначить полученные в итоге области.

Опираясь на условия задачи, составим уравнения:

  1. Крейсер | Линкор: 1 + 2 + 3 = 7000

  2. Крейсер: 1 + 2 = 4800

  3. Линкор: 2 + 3 = 4500

Чтобы найти Крейсер & Линкор (обозначенный на чертеже как область 2), подставим уравнение (2) в уравнение (1) и выясним, что:

4800 + 3 = 7000, откуда получаем 3 = 2200.

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

2 + 2200 = 4500, откуда 2 = 2300.

Ответ: 2300 - количество страниц, найденных по запросу Крейсер & Линкор.

Вывод

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

  1. Записать краткое условие.

  2. Выполнить рисунок.

  3. Записать данные в круги Эйлера.

  4. Анализировать, рассуждать и записывать результаты в части круга.

  5. Записать ответ.

Задачи:

1. Сколько существует натуральных чисел, меньших 1000, которые делятся на 3 , но не делятся на 2 и на 5?

2. Сколько существует различных десятизначных чисел, состоящих только из нулей и единиц, которые содержат не более трех единиц ?

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

4. По результатам одного социологического исследования, было установлено, что из 200 людей смотрящих телевизор, 110 человек смотрят спортивную передачу, 120 – комедии, 85 предпочитаю драмы, 50 смотрят драмы и спорт, 70 – комедии и спорт, 55 смотрят комедии и драмы и 30 человек смотрят все три вида передач. Сколько человек, смотрят спорт или комедии или драмы? сколько человек не смотрят ничего из вышеперечисленного?

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

6. Найти количество трехзначных чисел, которые делятся на 7, но не делятся на 2 и на 5.

7. На данный момент, в классе 20 учеников, получивших сначала учебного года, хотя одну двойку, 17 учеников, получивших не менее двух двоек, 8 учеников, получивших не менее трех двоек, три ученика получивших не менее 4 двоек, один ученик получивший 5 двоек, больше пяти двое нет ни у кого. Сколько всего двое в журнале?

Задача 1.

Решение:

Определение: множество А называется подмножество множества В, если каждый элемент множества А принадлежит множеству В.

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

Например, в задаче № 1 универсальным множеством можно считать множество чисел, от 1 до 999.

A = количество элементов во множестве А

В = 333

Если число делится на 2 и 3, то число делится на 6

A В = 166

Если число делится на 3 и 5, то число делится на 15

В D = 66

При таком подсчете, мы дважды посчитали числа, которые входят во множество

АВD = 33

(В/А)/D = В - AВ - ВD + AВD = 333 – 166 – 66 + 33 = 134

Задача 2

Определение: Правило суммы.

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

С = = 1-0 единиц

С = = 10-1 единица

С = = 45

С = = 120

120+45+10+1=176

Задача 3.

С = = 1 способ – 0 промахов

C = = 20 способов – 1 промах

С = = 190 способов – 2 промаха

С = =1140 способов – 3 промаха

С = =4845 способов – 4 промаха

Всего 1 + 20 + 190 +1140 + 4845= 6196 способов

Задача 4.

Формула включений и исключений

А ВD = A + В +D - AВ - AD - ВD - AВD

а) А ВD = 110 + 120 + 85 – 70 -55 – 50 + 30 =170

б)200-170=30 человек ничего не смотрят

Задача 5.

Составим таблицу друзей

С = = 10 компаний из 1 человека

С = = 45 компаний из 2 человек

С = = 120 компаний из 3 человек

С = = 210 компаний из 4 человек

С = = 252 компании из 5 человек

С ==210 компаний из 6 человек

С = = 120 компаний из 7 человек

С = =45 компаний из 8 человек

С = =10 компаний из 9 человек

С = = 1 компания из 10 человек

Итого 10+45+120+210+252+210+120+45+10+1= 1023 способов

Задача 6.

Всего 900 трехзначных чисел.

A = 900:7=128 чисел

АВ =900:14=64 числа

АD = 900: 35=25 чисел

АВD =900:70=12 чисел

А = А - АВ - АD + АВD = 128 – 64 – 25 + 12 = 51 число

Задача 7.

Найдем количество учеников, получивших ровно четыре двойки.

  1. 3 – 1= 2 ученика получили 4 двойки

Теперь узнаем количество учеников , получивших ровно три двойки, ровно две двойки и ровно одну двойку.

  1. 8 – 2 - 1 = 5 учеников получили 3 двойки

  2. 17 – 5 – 2 – 1 = 9 учеников получили 2 двойки

  3. 20 – 9 – 5 – 2 – 1 = 3 ученика получили 1 двойку

  4. 1×3 + 2×9 + 3×5 + 4×2 + 5×1 = 49 двоек в журнале

Вывод

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

Заключение

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

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

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

Круги Эйлера – не просто занимательная и интересная штука, но и весьма полезный метод решения задач. Причем не только абстрактных задач на школьных уроках, но и вполне себе житейских проблем. Они заставляют задумываться, подходить к решению какой-либо проблемы с разных сторон, уметь выбирать из множества способов решения наиболее простой, легкий путь. Сам Леонард Эйлер говорил: «круги подходят для того, чтобы облегчить наши размышления».

Список использованной литературы

  1. Галеева Р. А. Тренируем мышление. Задачи на сообразительность / Р. А. Галеева, Г. С. Курбанов, И. В. Мельченко – Изд. 2 – е – Ростов н/Д: Феникс, 2006.

  2. Игнатьев. Е.И. В царстве смекалки, или Арифметика для всех: Книга для семьи и школы. Опыт математической хрестоматии в 3 книгах/Худож. Н.Я. Бойко. – Ростов н/Д: Кн. Изд-во, 1995.

  3. Рыбников К.А.Комбинаторный анализ. Очерки истории.-М.: Изд.мехмата МГУ1996.-124с.

  4. История математики под редакцией Юшкевича А.П. М.: Наука Том 1.С древнейших времен до начала Нового времени.1970.

  5. Нагибин Ф.Ф., Канин Е.С. Математическая шкатулка: Пособие для учащихся 4-8 кл. сред. Шк. – 5-е изд. – М.: Просвещение, 1988.

  6. Увлекательные логические задачки, которые будут интересны детям и взрослым. http://logika.vobrazovanie.ru

Приложение

Приложение 1.

Приложение 2.

Приложение 3.

Приложение 4.

Якоб Бернулли.

Приложение 5.

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

Пал Эрдеш.

Приложение 6.

Приложение 7.

Приложение 8.

Приложение 9.

Просмотров работы: 7674