Решение проблемы выбора математическими методами

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

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

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

Этапы работы:

1. Работа по выбору темы исследования. Составление плана работы.

2. Разработка проекта: изучение и обобщение методов решения комбинаторных задач, сбор материала ( работа в библиотеке, в Интернете), решение задач и разделение их на группы в соответствии с методами решения.

3. Работа над проектом: оформление результатов работы. Создание презентации. Защита исследовательской работы.

Предмет исследования: комбинаторные задачи.

Объект исследования: методы решения.

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

Задачи исследования: изучить методы решения задач, рассмотреть различные ситуации, возникающие при решении задач, научиться решать комбинаторные задачи.

Методы: эмпирический – эксперимент, наблюдение, сравнение; математический – визуализация данных, статистика результатов.

1. Основная часть

1. 1Анализ теоретического материала

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

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

Самый простой способ - перебор возможных вариантов.

1. В коробке лежат 4 шара: белый, красный, синий, зелёный. Из неё вынимают 2 шара. Сколько существует способов сделать это ?

Решение: Переберём все возможные варианты: белый - красный, белый – синий, белый – зелёный, красный – синий, красный – зелёный, синий – зелёный. Ответ: 6 вариантов.

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

Правило сложения: если элемент А можно выбрать m способами , а элемент В n способами , причем любой выбор А отличен от В, то выбор или А или В можно сделать m+n способами.

2. Мама может дать сыну в школу какой-то один фрукт, имея три яблока, пять груш и семь бананов. Сколько разных способов выбора фруктов есть у мамы?

Решение: очевидно, что 3+5+7=15

Самый основной метод - правило умножения.

Для того чтобы найти число всех возможных исходов независимого проведения двух испытаний А и В, следует перемножить число всех исходов испытаний А и число всех исходов испытания В.

3. В меню школьной столовой 2 разных супа, 4 вторых блюда и 3 вида сока. Сколько можно составить вариантов обеда из 3 блюд?

Решение: Существует два варианта первого блюда, четыре варианта второго и три варианта сока. Значит 2*4*3=24 варианта составления обеда. В этой задаче используется правило умножения.

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

Итак дерево возможных вариантов для данной задачи.

Суп1 Суп2

В1 В2 В3 В4 В1 В2 В3 В4

Сок1 сок2 сок3 Сок1 сок2 сок3 Сок1 сок2 сок3 Сок1 сок2 сок3 Сок1 сок2 сок3 Сок1 сок2 ок3 Сок1 сок2 сок3

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

Определение. Произведение первых подряд идущих n натуральных чисел обозначают n! n! = 1*2*3*****(n-2)*(n-1)*n

Каждая перестановка расставляет, или переставляет все элементы множества в некотором порядке. Число перестановок множества из n элементов обозначают. Формула вычисления : !

4. На дверях четырех одинаковых кабинетов надо повесить таблички с фамилиями четырех заместителей директора. Сколькими способами можно это сделать?

Решение: P=5! =1*2*3*4*5=120

Определение. Упорядоченные k-элементные подмножества, содержащие k элементов из данного n–элементного множества, называют размещениями без повторений из n элементов по k.

Их число обозначают A=n*(n-1)* **(n-k+1)=

5. Сколькими способами из 25 учеников класса можно выделить актив в следующем составе: культорг, физорг, редактор стенгазеты?

Решение: Надо выделить троих из 25 ,то есть найти число размещений без повторений из 25 по3.

Определение. Неупорядоченное подмножества, содержащие k элементов из данного n –элементного множества, называют сочетаниями без повторений из n элементов по k, а их число обозначают символом.

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

6. Мартышка, осел, козел и мишка захотели сыграть квартет. Выбирают 4 инструмента из 11.

Решение:

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

Волейболисты меняются местами.

Тренер волейбольной команды решил изменить расположение игроков.

-Следующую встречу будем начинать по-другому,- объявил он после очередного проигрыша. - Ты, Сергей, встанешь на подачу; Володя - на четвёртый номер, в нападение, а ты, Николай

- А если опять проиграем? - спросил капитан.

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

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

Как же подсчитать, сколькими способами можно расставить 6 волейболистов на 6 различных мест?

Решение: Р= n!=6*5*4*3*2*1=720

Обед в кафе

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

1-й. давайте сядем в алфавитном порядке, тогда никому не будет обидно.

2-й. Нет, сядем по возрасту

5-й. Предлагаю сесть по росту, и никаких проблем.

6-й. Устроим здесь физкультуру, не так ли?

7-й. Придётся тащить жребий.

1-й. По-моему, уже обед остыл.

2-й. Я сажусь, где понравиться, и вы давайте за мной.

Официант - Вы ещё не расселись? Друзья мои, оставьте ваши пререкания. Сядьте за стол как кому придется, и выслушайте меня. (Все сели как попало)

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

Друзья. - Вот здорово, будем каждый день обедать у вас.

Официант. Друзьям не пришлось дождаться того дня, когда они стали питаться бесплатно. И не потому, что официант не исполнил обещания, а потому, что число всех возможных размещений за столом чересчур велико. Оно равняется ни мало, ни много – 40320. Такое число дней составляет, как нетрудно сосчитать, почти 110 лет!

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

Решение. В нашем случае число перестановок равно 1*2*3*4*5*6*7*8=40320.

Простые методы

Простой перебор Правило сложения Правило умножения Дерево возможных вариантов

Содержание Если элемент А можно Для того, чтобы найти числоГрафическое изображение выбрать m способами , а всех возможных исходов элемент В n способами , независимого проведения причем любой выбор А двух испытаний А и В, отличен от В, то выбор или следует перемножить число

А или В можно сделать m+n всех исходов испытаний А и способами. число всех исходов испытания В.

Применение При решении простых задач, Выбор «или А или В. » Выбор «и А и В » Когда число вариантов много когда число возможных вариантов невелико

Комбинаторные методы

Обозначение Определение Формула Признаки

Перестановки P Каждая перестановка расставляет,! Размещения из n элементов или переставляет все элементы по n элементов называют множества в некотором порядке перестановками из n элементов

Размещения A Упорядоченные k-элементные A=n*(n-1)* (n-k+1)= Важен порядок выбора

(без повторений) подмножества, содержащие k элементов (то есть их элементов из данного место в соответствующем n–элементного множества, упорядоченном наборе)

называют размещениями без повторений из n элементов по k.

Сочетания (без повторений) Неупорядоченное подмножества, Не важен порядок выбора содержащие k элементов из элементов (то есть их данного n –элементного место в соответствующем множества, называют сочетаниями упорядоченном наборе)

без повторений из n элементов по

2. Систематизация задач по методам решения

2. 1 Простые методы

1. Мама может дать сыну в школу какой-то из фруктов, имея 3 яблока, 5 груш и 7 бананов. Сколько разных способов выбора фруктов есть у мамы?

Решение: способ сложения, очевидно, что существует всего 3+5+7=15 вариантов выбора фруктов по одному.

2. Из пункта А в пункт Б можно добраться самолётом, поездом и автобусом, причём между этими пунктами существуют 2 авиалинии, 2 железнодорожных и 3 автобусных маршрута.

Решение: общее число возможных маршрутов равно 2+1+3=6

3. В магазине «Всё для чая» есть 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить пару «чашка-блюдце»? В магазине есть ещё 4 чайные ложки. Сколько наборов из 3 предметов можно составить?

Решение: применим правило умножения, выберем чайную пару. Сначала выберем одну из 5 чашек: возможность выбора даёт всего 5 вариантов; далее для чашки выберем одно из 3 блюдец. Итак, возможное число пар равно 5*3=15. Для каждой выбранной пары можем взять одну из 4 чайных ложек, тогда число возможных наборов из 3 предметов равно 5*3*4=60.

4. Сколькими способами можно разместить 4 шара по двум лункам, если в каждую помещается только 1 шар?

Решение: очевидно, что первую лунку можно заполнить четырьмя способами, т. к. при выборе первой лунки имеется 4 шара. Вторую лунку можно заполнить одним из 3 оставшихся шаров. Заметим, что с каждым из способов заполнения первой лунки может совпасть любой из способов заполнения второй лунки, поэтому общее число способов распределения шаров по двум лункам равно 4*3=12.

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

Решение: белый король может стоять или в углу шахматной доски, или у её края, или внутри шахматной доски.

Если белый король стоит в углу шахматной доски, то чёрный может быть поставлен в любые 60 клеток доски, которые расположены на расстоянии более одной клетки от белого; угловых клеток 4, поэтому по правилу произведения имеем 4*60 вариантов.

Если белый король стоит у края доски (но не в углу), а таких вариантов расстановки всего 6*4=24, то чёрный король может быть поставлен в одну из 58 клеток, которые не находятся под «боем» белого короля; такая расстановка по правилу произведения допускает 24*58 вариантов.

Для случая, когда белый король стоит не у края доски (таких клеток 36), чёрный король может быть поставлен в одну из 55 клеток, которые не находятся «под боем» белого короля. По правилу произведения имеем 36*55 вариантов.

Применяя правило суммы, получаем 4*60+24*58+36*55=3612 возможных расстановок двух королей на доске.

6. Из класса, в котором учится 15девочем и 10 мальчиков, нужно выбрать одну девочку и одного мальчика для ведения школьного вечера. Сколькими способами это можно сделать?

Решение: если девочек 15, а мальчиков 10, а надо выбрать одного мальчика и одну девочку, то 10*15=150 вариантов. В этой задаче используется правило умножения.

7. В чемпионате города по футболу играет 10 команд. Сколькими способами могут распределиться 3 призовых места?

Решение: На первое место претендует 10 команд, на 2 место - 9 команд, т. к. первое место уже занято, на 3 место - 8 команд, т. к первые 2 места уже заняты. Значит 10*9*8=720 вариантов. В этой задаче используется правило умножения.

8. В расписании уроков на среду для первого класса должно быть четыре урока: 2 урока математики, урок чтения и урок физкультуры. Сколькими способами можно составить расписание на этот день.

Решение: Если первым будет урок чтения, то вторым можно будет поставить урок физкультуры, после этого для уроков математики остаётся один вариант постановки в расписание. Значит 4*3=12 вариантов расписания на этот день. В этой задаче используется правило умножения.

9. В конференции участвовало 30 человек. Каждый участник с каждым обменялся визитной карточкой. Сколько всего понадобилось карточек?

Решение: Если в конференции участвовало 30 человек, то каждый раздал 29 визиток. Значит, 30*29=870 визиток было роздано. В этой задаче используется правило умножения.

10. Сколько чётных двухзначных чисел можно составить из цифр 0, 1, 2, 4, 5, 9.

Решение: по правилу произведения -5цифр могут быть десятками, 3 цифры могут быть единицами. 5*3=15 чисел.

11. На завтрак можно взять плюшку, бутерброд, пряник или кекс. А запить можно соком, кофе или кефиром. Сколько существует комбинаций на завтрак, если можно взять 1 блюдо и 1 напиток?

Решение: 4*3=12

12. В коридоре 3 лампочки. Сколько существует способов осветить коридор?

Решение: 2*2*2=8

13. 6 граней кубика отмечены цифрами: 1, 2, 3, 4, 5, 6. Кубик бросают 2 раза и записывают выпавшие цифры. Найдите число всех возможных вариантов.

Решение: 6*6=36

14. Сколькими способами могут распределяться золотая,серебренная медали по итогам первенства по футболу, если число команд 12?

Решение:12*11=132

2. 2 Комбинаторные методы

1. 10 разных писем раскладывают по 1 в 10 конвертов. Сколько способов расклада существует?

Решение: P=1*2*3*4*5*6*7*8*9*10= 10! =3628800способов

2. Вова услышал в песне, что зимам дают имена. Он вспомнил семь самых хороших зим и дал им женские имена.

1) Сколько существует комбинаций? (7!)

2) Сколько существует способов, если первая- Татьяна, а седьмая- Анна? (5!)

3. Одиннадцать футболистов строятся перед матчем. Первый- капитан, второй- вратарь, а остальные - случайно. Сколько существует вариантов постановки?

Решение: 9!

4. В классе 27 учеников, к доске вызвать двоих. Сколько способов, если:

А) 1-ый ученик решает задачи по алгебре, 2-ой ученик - по геометрии

Б) они должны быстро стереть с доски

5. В классе 7 человек успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде?

Решение:

6. Осёл, козёл, мишка, мартышка затеяли сыграть квартет. Сколькими способами они смогут:

А) по одному сесть за выбранные четыре инструмента.

Решение: Р= 4!= 24

Б) выбрать 5 инструментов из 12 данных.

Решение: С512=

7. В классе 16 девочек и шесть мальчиков. Нужно выделить группу из 3х человек для организации классного часа. Сколькими способами это можно сделать, если:

А) группа должна состоять только из девочек;

Решение:

Б) группа должна состоять только из мальчиков?

Решение:

8. В классе 27 учеников. Выбрать трех для дежурства. Сколько способов, если:

А) 1-ый решает задачу, 2-ой сходит за мелом, 3-ий пойдет в столовую

Решение: =27*26*25=17550

Б) им спеть хором

Решение:

9. Встретились несколько человек и стали здороваться друг с другом. Известно, что рукопожатий было от 60 до 70. Сколько человек встретилось, если:

А) Каждый здоровался с каждым

Решение: Пусть встретилось n человек, двое здороваются n * (n-1)> 120 n= 12

61 рукопожатие

10. Встретились 11 футболистов и 6 хоккеистов, и каждый с каждым стал играть 1 раз в шашки.

1). Сколько встреч было между футболистами?

Решение:

2). Сколько встреч было между хоккеистами?

Решение:

3). Сколько встреч было между футболистами и хоккеистами?

Решение: (11*6=66)

4)Сколько было встреч?

Решение:

11. В классе 30 учащихся. Сколькими способами можно назначить двух дежурных?

Решение: порядок неважен = 435

12. На тренировках занимаются 12 баскетболистов. Сколько может быть образовано стартовых пятёрок?

Решение : сочетание (порядок не важен ). ; 792

13. Для отправки на Марс нужен экипаж : командир, первый помощник, второй помощник, два бортинженера и врач. Командиры могут быть избраны из 25 лётчиков. Бортинженеры из 20 инженеров. Врачи из 8 медиков.

Каким способом можно укомплектовать экипаж?

Решение: командир, 1-ый помощник, 2-ой помощник (порядок важен ) ,Бортинженеров: = 190, Выбор врача: = 8,Выбор экипажа 13800 * 190 * 8 =20976000

14. Команда из 50 человек обменялись рукопожатиями. Сколько было рукопожатий?

Решение: Порядок не важен

15. 12 солдат нужно в разведку послать 5. Сколькими способами это можно сделать?

Решение:

16. «Проказница мартышка, осёл, козёл и косолапый мишка затеяли сыграть квартет». На складе 12 музыкальных инструментов. Мишке поручили принести со склада 8 любых инструментов. Сколько вариантов выбора есть у Мишки?

Решение:

17. Из 15 членов группы надо выбрать 3 дежурных. Сколькими способами можно сделать этот выбор? Решение:

18. В магазине продается 8 различных наборов марок, посвящённых «Дню 8 Марта «. Сколькими способами можно сформировать из них 3 набора?

Решение:

3. Из истории комбинаторики

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

В документах, относящихся к началу нашей эры, упоминаются «четырёхгранные» или «пирамидальные» числа, представляющие собой. «Треугольными» называются числа вида ; придавая значения 1, 2, 3, 4, получим « треугольные» числа 1, 3, 6, 10

Во всех странах мира люди с давних времён играли в кости. Особенно широкое распространение получили азартные игры с развитием денежного обращения. Сиятельные графы и морские пираты, византийские купцы и золотоискатели Невады, блистательный д’Артаньян и его товарищи мушкетёры – все были заражены азартом этой древней игры. Атос оценил своего слугу Гримо в десять ставок; выигрыши и проигрыши состояний, дворцов, поместий хорошо известны в истории. Игра распространилась настолько, что христианской церкви пришлось издавать указы и постановления, запрещавшие или ограничивавшие игру. Участникам третьего крестового похода не разрешалось проигрывать более 20 шиллингов в сутки. Людовик IX запретил не только игру, но даже изготовление костей. Издавались законы о запрещении игры и на Руси.

В XVII веке в Европе стали распространятся таблицы, в которых перечислялись возможности получения разного числа очков на двух и трёх костях. Математики стали анализировать комбинации, получающиеся при бросании костей. Этими вопросами занимались такие известные итальянские математики 16 века, как Д. Кардано, Н. Тарталья. В 18 веке - Галилео Галилей, но его рукопись оставалась неопубликованной до 1718 года.

Наиболее полно сделали это Паскаль и Ферма. Паскаль и Ферма излагали свои результаты в письмах. В 1653 году Паскаль писал друзьям подготовительной им рукописи; однако его «Трактат об арифметическом треугольнике» был опубликован посмертно лишь в 1665 году.

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

Подсчёт возможностей при игре в кости привёл в XVII и XVIII веках к развитию важной области математики – теории вероятностей.

Современный вид формулы комбинаторики приобрели к началу XIX века; в это время уже почти полностью сформировалась и современная алгебраическая символика.

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

4. Некоторые факты о применении комбинаторики

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

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

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

Заключение

В работе над проектом мы изучили: правила простого перебора, сложения, умножения, дерево возможных вариантов, понятие факториала, определения перестановки, размещения, сочетания и систематизировали их по признакам применения.

Занимались поиском задач в библиотеке, в Интернете, и их решением.

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

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