XXIV Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Основы комбинаторики для школьников 9-11 классов
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
ВВЕДЕНИЕ
Данная работа посвящена видам комбинаторных задач и методам их решениям. При подготовке к ОГЭ по математике, я обратила внимание на то, что в школьном курсе алгебры, не уделяется должное внимание такому разделу, как комбинаторике. Поэтому часто школьники боятся этой темы, и надеются на то, что данная тема не подается им на экзамене. В своей работе я постараюсь раскрыть данную тему, и привести различные методы решения комбинаторных задач. Комбинаторика помогает рассчитывать все возможные варианты решения задачи при заданных ограничениях, анализировать статистические данные, определять оптимальные игровые стратегии. А также развивает логическое мышление, аналитические способности, креативность, умение работать с абстрактными концепциями, упорство и терпение
Цель работы: изучение методов решения основных видов комбинаторных задач и составление комплекса задач на применение формул комбинаторики.
Задачи работы:
1. Рассмотреть основные формулы
2. Привести примеры решения задач на число размещений, сочетаний и перестановок
3. Рассмотреть основные элементы комбинаторики
Объект исследования: задачи комбинаторики
Предмет исследования: методы решения основных видов комбинаторных задач
ГЛАВА 1. ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ.
1.1 Зарождение комбинаторики как науки
Первоначально, комбинаторика была приложенной наукой, используемой в играх и азартных развлечениях.
Одним из первых занялся подсчетом различных комбинаций при игре итальянский математик Тарталья. Он составил таблицу, показывающую, сколькими сколькими способами могут выпасть костей, но при этом не учитывалось, что одна и та же сумма очков может быть получена разными способами. Теоретическое же исследование вопросов комбинаторики предприняли в XVII веке французские ученые Паскаль и Ферма. Паскаль решил задачу о разделе ставки в общем случае, когда одному игроку остается до выигрыша r партий, а второму s партий. Дальнейшее развитие комбинаторики связано с именами Якова Бернулли, Лейбница и Эйлера.
1.2 Основные обозначения и определения, встречающиеся при изучении комбинаторики
- множество натуральных чисел
- множество целых чисел
- множество рациональных чисел
- целая часть числа х (наибольшее целое, не превосходящее х)
- дробная часть числа
- факториал:
- последовательность
- функция Эйлера
- количество положительных делителей числа п
- сумма положительных делителей числа п
- числа Фибоначчи
Определение 1. Факториал числа — это произведение всех положительных целых чисел, меньших или равных .
Определение 2. Сочетание — это набор элементов, который можно выбрать из множества без учёта порядка.
Определение 3. Перестановка — это способ последовательно расположить элементы во множестве.
Определение 4. Размещение — это упорядоченный набор элементов, который можно выбрать из множества.
Определение 5. Множество — это перебираемый набор элементов
Определение 6. Выбор — это действие, при котором из множества достаются какие-то составляющие.
Определение 7. Расположение — это действие, при котором расставляются выбранные элементы в определённом порядке
Определение 8. Разбиение — это представление множества в виде объединения произвольного количества попарно непересекающихся непустых подмножеств.
Определение 9. Подмножество — это часть совокупности элементов, которую выбирают из данного множества в соответствии с определёнными правилами.
1.3 Общие правила комбинаторики
Определение 10. Правило суммы. Если некоторый объект можно выбрать способами, а другой объект можно выбрать способами, то выбор “либо , либо ” можно осуществить способами
Замечание: при использовании правила суммы надо следить, чтобы ни один из способов выбора объекта не совпадал с каким-нибудь способом выбора объекта . Если такие совпадения есть, то правило суммы утрачивает свою силу, и мы получаем лишь способов выбора, где - число совпадений.
Определение 11. Правило произведения. Если объект можно выбрать способами и если после каждого такого выбора, объект можно выбрать способами, то выбор “и и ” в указанном порядке можно осуществить способами
1.4 Основные элементы комбинаторики
-
Количество перестановок
-
Количество перестановок с повторениями
-
Количество сочетаний
-
Количество сочетаний с повторениями
-
Количество размещений
-
Количество размещений с повторениями
1.5 Связь комбинаторики с другими разделами математики
Теория вероятностей. Комбинаторика играет важную роль в вычислении вероятностей событий. Используя комбинаторные методы, можно подсчитать количество благоприятных исходов и общее количество возможных исходов.
Теория графов. Графы используются для моделирования комбинаторных структур и отношений между объектами. Комбинаторные методы помогают решать задачи, связанные с структурами графов.
Дискретная математика. Комбинаторика является одной из основ дискретной математики, которая изучает алгоритмы, структуры данных и дискретные объекты. Методы комбинаторики применяются в алгоритмах и теории вычислений.
Теория чисел: Некоторые комбинаторные задачи связаны с делимостью и свойствами чисел. Вопросы о числе способов представить число в виде суммы, разделения на части и др. имеют комбинаторные решения.
Статистика. Комбинаторика используется для построения выборок, оценки вероятностей и анализа данных. Она помогает в разработке статистических методов, включая анализ вариаций и корреляции.
Глава 2. РЕШЕНИЕ КОМБИНАТОРНЫХ ЗАДАЧ ДЛЯ ШКОЛЬНИКОВ 9-11 класса
2.1 Задачи на число перестановок и перестановок с повторениями
Задача на число перестановок
Условие: сколько различных способов существует расставить 8 книг на полке?
Решение: подставим значение в формулу
Ответ:
Задача на число перестановок с повторениями
Условие: У Вас есть 7 Шаров: 3 фиолетовых, 2 желтых и 2 оранжевых. определите, сколько различных способов можно расположить эти шары в ряд
Решение:
1)подставим значения в формулу
2)найдем факториалы
= 5040
3)
Ответ:
2.2 Задачи на число размещений и размещений с повторениями
Задача на число размещений
Условие: В цехе работают 10 кузницей. Сколькими способами можно поручить четырем из них изготовить четыре различные детали по одной на каждого?
Решение:
Задача на число размещений с повторениями
Условие: Сколькими способами можно разделить 8 мандаринов между четырьмя ребятами?
Решение: подставим значения в формулу
Ответ:
2.3 Задачи на число сочетаний и число сочетаний с повторениями
Задача на число сочетаний
Условие: В корзине лежит 6 апельсинов и 8 абрикосов. Нужно выбрать 3 апельсина и 6 абрикосов. Сколькими способами можно это сделать?
Решение:
Так как нам нужно выбрать и апельсин, и абрикос, то у нас действует правило произведения
Задача на число сочетаний с повторениями
Условие: Сколькими способами можно распределить между 5 делопроизводителями 10 пачек бумаги?
Решение:
2.4 Задачи на развитие функциональной грамотности
Задача 1. Лидия Ивановна и ее дочь Вера часто играли в лото. Каждая брала по три карточки, Вера хорошо перемешивала бочонки в мешке, затем доставала из мешка очередной бочонок с числом от 1 до 90, называла его, и тот, у кого на карточке обнаруживалось это число, закрывал его бочонком.
Однажды Вера заметила, что довольно часто, первым доставался один и тот же бочонок, но первые два бочонка, всегда были разные, и тогда она задалась вопросом: много ли способов извлечь один за другим два бочонка из мешка, если в нем их 90?
Решение: тогда вера построила таблицу, в которой слева написаны возможные варианты для 1 бочонка, а сверху для второго.
|
1\2 |
1 |
2 |
3 |
4 |
…. |
89 |
90 |
|
1 |
1;2 |
1;3 |
1;4 |
….. |
1;89 |
1;90 |
|
|
2 |
2;1 |
2;3 |
2;4 |
….. |
2;89 |
2;90 |
|
|
3 |
3;1 |
3;2 |
3;4 |
….. |
3;89 |
3;90 |
|
|
4 |
4;1 |
4;2 |
4;3 |
….. |
4;89 |
4;90 |
|
|
…. |
…. |
…. |
…. |
…. |
…. |
…. |
|
|
89 |
89;1 |
89;2 |
89;3 |
89;4 |
….. |
89;90 |
|
|
90 |
90;1 |
90;2 |
90;3 |
90;4 |
….. |
90;89 |
Так как один и тот же бочонок нельзя вытащить два раза, то по диагонали в таблице, поставлен -невозможное событие. Тогда вера поняла, что если для первого бочонка всегда 90 вариантов, то для второго 89 вариантов.
А мы с вами уже знаем, что раз нам нужно извлечь и 1 бочонок и 2 бочонок, то действует правило произведение, значит всего способов извлечь один за другим два бочонка будет способов.
Примечание: похожие таблицы используются при составлении сетки матчей в футболе, баскетболе, хоккее и других спортивных играх, что лишний раз подчеркивает значимость комбинаторики в жизни.
Задача 2. Довольно часто, для поиска возможных вариантов событий используют “дерево событий”.
Алгоритм построения дерева:
-
Берется первая точка. Из нее проводится столько отрезков, сколько различных способов можно сделать на первом шагу.
-
Затем из конца каждого отрезка, проводят столько отрезков, сколько различных способов можно сделать на втором шагу.
-
Дальнейшие шаги аналогичны, и зависят от количества шагов
Рассмотрим задачу с командой космического корабля.
Известно, что при составлении команд космических кораблей возникает вопрос о психологической совместимости участников космического путешествия. Предположим, что надо составить команду из трех человек: командира, инженера и врача.
Пусть на место командира будет четыре кандидата , на место инженера три кандидата: и на место врача тоже три кандидата . Проверка показала, что командир совместим с инженерами и и врачами . Командир - с инженерами и всеми врачами. Командир - с инженерами и врачами . Командир - со всеми инженерами и врачом . Помимо этого, инженер психологически несовместим с врачом , инженер - с врачом и инженер - с врачом .
Сколькими способами при этих условиях может быть составлена команда корабля?
Построим дерево событий:
Рисунок 1. дерево событий задачи 2
Из рисунка видно, что всего таких способов 10.
Примечание: стоит отметить, что, по сути, данная задача решается за счет правила сложения, ведь мы выбираем “либо , либо ,либо , либо ” и складываем их возможные комбинации
Задача 3. В данной задаче я хочу показать, как комбинаторика помогает решить лингвистические проблемы.
Лингвистам - специалистам по живым и мертвым языкам - часто приходится разгадывать надписи, сделанные на незнакомых языках. Предположим, что им попался текст, написанный при помощи 10 незнакомых знаков. Каждый знак является буквой, изображающий один из 10 звуков.
Сколькими способами можно сопоставить звуки знакам письма?
Расположим знаки письма в некотором порядке, тогда имеем перестановок. Проверить столько вариантов работа тяжелая. Попробуем упростить задачу. Предположим, что нам удалось найти, 6 знаков для гласных и 4 для согласных. Тогда гласные переставляются только между собой, так же, как и согласные. Тогда имеем: теперь стало гораздо проще, и вычислительные машины смогут без труда сопоставить знаки и звуки. Таким образом знание комбинаторики, может упростить процесс решения лингвистических проблем
ЗАКЛЮЧЕНИЕ
Данная работа нацелена на помощь в решении комбинаторных задач для школьников и включает в себя различные методы решения комбинаторных задач и виды комбинаторных задач. Я считаю, что достигла своей цели, и выполнила все задачи работы.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Виленкин Н. Я., Комбинаторика, Москва, Наука, 1969.
2. Алфутова Н. Б. Устинов А. В. Алгебра и теория чисел. Сборник задач для математических школ. - М.: МЦНМО, 2002.— 264 с.
3. Бабичева T.A.Учебное пособие
«Решение комбинаторике» (практикум) - Махачкала: ДГУНХ, 2018. - 44 с.
4. Skillbox: Что такое факториал и как его вычислить https://skillbox.ru/media/code/chto-takoe-faktorial-i-kak-ego-vychislit/
5. Skillbox: Перестановки, сочетания и размещения: стартер-пак по комбинаторике для IT (https://skillbox.ru/media/code/perestanovki-sochetaniya-i-razmeshcheniya-starterpak-po-kombinatorike-dlya-it/)https://skillbox.ru/media/code/perestanovki-sochetaniya-i-razmeshcheniya-starterpak-po-kombinatorike-dlya-it/
6. Mathprofi: Основные формулы комбинаторики http://www.mathprofi.ru/formuly_kombinatoriki.pdf
7. Infourok: Комбинаторика. Перестановки. Формула для числа перестановок https://infourok.ru/kombinatorika-perestanovki-reshenie-zadach-661504.html?ysclid=m45fmc7kgq882972712
8. Multiurok: Комбинотрные задачи: размещения https://multiurok.ru/files/kombinatornyie-zadachi-razmieshchieniia.html?ysclid=m5tdqzc0zf309501709
9. Беляева Т.Ю. Элементы комбинаторики