Исследовательская работа "Решение комбинаторных задач"

Решение комбинаторных задач

Исследовательская работа

Содержание

1.     Введение………………………………………………………….…....стр. 3

2.     Комбинаторные задачи (введение в историю).....………..................стр. 4

3.     Поиск закономерностей……………………………………..………..стр. 5

4.     Перебор возможных вариантов. Дерево возможных  вариантов…..стр. 6

5.     Правило суммы и произведения…….……………………………......стр. 9

6.     Заключение…………………………………………………………....стр. 11

7.     Список литературы………………………………………...................стр. 11

1.     Введение

В нашу жизнь властно вошли выборы и референдумы, банковские кредиты и страховые полисы, таблицы занятости и диаграммы социологических опросов. Общество все глубже начинает изучать себя и стремиться сделать прогнозы о самом себе и о явлениях природы, которые требуют представлений о вероятности. Даже сводки прогноза валют на мировых рынках по телевизору и в газетах сообщают о том, что "завтра ожидается падение котировок с вероятностью 5%". И, конечно же, мне стало интересно, было ли возникновение данной теории случайным явлением в науке?

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

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

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

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

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

1)  изучение и анализ современной литературы;

2)  поиск способов решения комбинаторных задач;

3) решение комбинаторных задач;

4) составление банка комбинаторных задач.

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

1)изучение и анализ учебно–методической литературы по проблеме исследования;

2)методы сравнения, обобщения и классификации;

3)обобщение и анализ теоретико-методического материала.

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

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

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

2.  Комбинаторные задачи (введение в историю)

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

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

     Комбинаторика – ветвь математики, изучающая комбинации и перестановки предметов. Еще комбинаторику можно понимать как перебор возможных вариантов. Комбинаторика возникла в XII веке. Долгое время она лежала вне основного русла развития математики.

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

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

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

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

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

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

Комбинаторика как наука стала развиваться в XIII веке параллельно с возникновением теории вероятностей, так как для решения вероятностных задач необходимо было подсчитать число различных комбинаций элементов. Первые научные исследования по комбинаторике принадлежат итальянским ученым Дж. Кардано, Н. Тарталье (1499-1557), Г. Галилею (1564-1642) и французским ученым Б. Паскалю (1623-1662) и П. Ферма. Комбинаторику как самостоятельный раздел математики первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666 году. Он также впервые ввел термин «комбинаторика». Значительный вклад в развитие комбинаторики внес Л.Эйлер.

3.    Поиск закономерностей.

Что такое закономерность? Это закон, правило, по которому записаны числа, расположены фигуры.

Решение примеров. Выявлять закономерности в числовых рядах.

·        Выявить закономерности и записать еще 4 числа:

·        Вставить пропущенные числа:

1)                24, 21, 19, 18, 15, 13, _ , _ , 7,6 (12, 9);

2)                1, 4, 9, 16, _ , _ , 49, 64, 81, 100 (25, 36);

3)                16, 17, 15, 18, 14, 19, _ , _ (13, 20);

4)                1, 3, 6, 8, 16, 18, _ , _ , 76, 78 (36, 38);

5)                7 26 19; 5 21 16; 9 _ 4 (13);

6)                2 4 8 10 20 22 _ _ 92 94 (44, 48);

7)                24 22 19 15 _ _ (10, 4).

·        Продолжить ряд:

1)    15 16 18 21 25 _ (30);

2)    2 5 8 11 _ (14);

3)    6 9 12 15 18 _ (21);

4)    16 12 15 11 14 10 _ _ (13, 9);

5)    3 7 11 15 18 _ (22).

·        Вставить пропущенное число

1)    ? : 2=3

2)    ? : 2=4

3)    ? : 2=5

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

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

Задача 1  Сколько двузначных чисел можно составить из цифр: 1, 4 и 7. (9)

Решение: для того, чтобы не пропустить и не повторить ни одно из чисел, будем записывать их в порядке возрастания. Сначала запишем числа, начинающиеся с цифры 1, затем с цифры 4, и, наконец, с цифры 7:

11, 14, 17, 41, 44, 47, 71, 74, 77.

Задача 2  В алфавите племени уауа имеются только две буквы – «а» и «у».

Сколько различных слов по три буквы в каждом слове можно составить, используя алфавит этого племени? (8)

Задача 3  На завтрак Вова может выбрать плюшку, бутерброд, пряник или кекс, а запить их он может кофе, соком или кефиром. Из скольких вариантов завтрака Вова может выбрать? (12)

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

Задача 5 Сколькими способами можно составить патруль из двух милиционеров, если на дежурство вышли четверо: Васечкин, Петров, Иванов и Сидоров?

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

Задача 7 Запишите все двузначные числа, которые можно составить из цифр 0, 1, 2, используя при записи числа каждую цифру один раз. Сколько получится чисел, если каждую цифру использовать не один раз?

Задача 8  Сергей, Андрей и Роман собрались потренироваться в бросании мяча в баскетбольную корзину. У них только один мяч, и им надо договориться, кто за кем будет бросать мяч в корзину. Сколькими способами они могут занять очередь?

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

Задача 10 В палатке имеется 3 сорта мороженого: рожок, брикет и эскимо? Наташа и Данил решили купить по одной порции каждого сорта мороженого. Сколько существует вариантов такой покупки?

Вывод: В данных примерах был осуществлен способ перебора возможных вариантов (возможных комбинаций). Решения данных задач основывается на общем правиле умножения.

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

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

Задача 1  В алфавите племени уауа имеются только две буквы – «а» и «у».

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

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

Задача 3 Имеются ручки четырех цветов: красные, синие, зеленые, черные – и два вида записных книжек. Сколько различных наборов из ручки и записной книжки можно составить из этих предметов?

Задача 4 Шифр для сейфа составляют из букв и цифр, причем на первом месте всегда ставится буква. Сколько различных вариантов шифра можно составить, используя буквы А, В, С и цифры 3, 7, 9?

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

Задача 6 Сколькими способами три друга могут разделить между собой два банана, две груши и два апельсина так, чтобы каждый получил по два различных фрукта?

Задача 7 Школьники из Волгограда собрались на каникулы поехать в Москву, посетив по дороге Нижний Новгород. Сколькими различными способами ребята могут осуществить свое путешествие, если из Волгограда в Нижний Новгород можно отправиться на теплоходе или поезде, а из Нижнего Новгорода в Москву – на самолете, теплоходе, поезде или автобусе?

Задача 8 Сколькими способами можно выбрать гласную и согласную буквы из слова «ЗДАНИЕ»?

5. Правило суммы и произведения

Правило сложения: если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить m+n способами.

Задача 1 На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?

Решение: По условию задачи яблоко можно выбрать пятью способами, апельсин – четырьмя. Так как в задаче речь идет о выборе «либо яблоко, либо апельсин», то его, согласно правилу сложения, можно осуществить 5+4=9 способами.

Задача 2 Сколько трехзначных чисел можно составить из цифр 1,3,5,7, используя в записи числа каждую из них не более одного раза?

Решение: составим дерево возможных вариантов.

Эту задачу можно решить по-другому и намного быстрее, не строя дерева возможных вариантов. Рассуждать будем так. Первую цифру трехзначного числа можно выбрать четырьмя способами. Так как после выбора первой цифры останутся три, то вторую цифру можно выбрать из оставшихся цифр уже тремя способами. Наконец, третью цифру можно выбрать (из оставшихся двух) двумя способами. Следовательно, общее число искомых трехзначных чисел равно произведению 4∙3∙2, т.е. 24.

Правило умножения: если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать п способами, то выбор пары (А, В) в указанном порядке можно осуществить m∙п способами.

Задача 1  Сколько пятизначных чисел можно составить из цифр 5, 9, 0, 6?

Решение: По правилу умножения получаем: 4∙4∙4∙4=256 чисел.

Задача 2  Из города А в город В ведут две дороги, из города В в город С – три дороги, из города С до пристани – две дороги. Туристы хотят проехать из города А через города В и С к пристани. Сколькими способами они могут выбрать маршрут?

Решение: Пусть из города А в В туристы могут выбрать двумя способами. Далее в каждом случае они могут проехать из В в С тремя способами. Значит, имеется 2∙3 вариантов маршрута из А в С. Так как из города С на пристань можно попасть двумя способами, то всего существует 2∙3∙2=12 способов выбора туристами маршрута из города А к пристани.

Задача 3  Из пункта А в пункт В можно попасть десятью путями, а из пункта В в пункт С – девятью путями. Сколько имеется маршрутов из пункта А в пункт С через пункт В?

Решение: 10∙9=90 маршрутов

Задача 4 В кафе имеются три первых блюда, пять вторых блюд и два третьих. Сколькими способами посетитель кафе может выбрать обед, состоящий из первого, второго и третьего блюд?

Решение: первое блюдо можно выбрать тремя способами, второе – пятью и третье – двумя, отсюда, по правилу умножения получаем 3∙5∙2=30 способами.

Задача 5 Сколько различных пятизначных чисел, делящихся на 10 можно составить из цифр 0, 1, 2, 3, 4? Каждую цифру можно использовать в записи только один раз.

Задача 6 Сколько пятизначных чисел, делящихся на три, можно составить из цифр 3, 4, 6, 7, 9 если каждое число не содержит одинаковых цифр?

Задача 7 Сколько шестизначных чисел можно составить из цифр 4, 5, 6, 7, 8, 9 так, чтобы каждое из них начиналось с комбинации «567»?

Задача 8 Сколько чётных положительных пятизначных чисел можно получить из цифр 1, 2, 3, 4?

6. Заключение

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

На базе этого материала можно решать более сложные задачи теории вероятности.

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

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

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

1.           Гнеденко Б. В., Журбенко, И. Г. Теория вероятностей и комбинаторика //Математика в школе. – 2007. - №6. – с. 67-70.

2.           Гусев В. А. Внеклассная работа по математике в 5-8 классах. /Под. ред. С. И. Шварцбурга. - М.: Просвещение, 1977. – 288с.

3.           Дихтярь М., Эргле Е. Исторические комбинаторные задачи и комбинаторные модели //Математика. – 2007. - №14. – с. 23-24.

4.           Математика: Учебник для 5 кл. общеобразоват. учреждений / Г. В. Дорофеев, С. Б. Суворова, И. Ф. Шарыгин и др.; под ред. Г. В. Дорофеева, И. Ф. Шарыгина. – 8-е изд. - М.: Просвещение, 2006. – 302с.

5.                 Овсянникова Л.В. Факультативный курс по математике //Начальная школа. – 2005. - №9. – с. 29-33.

6.           Виленкин Н. Я. Комбинаторика. – М.: Наука, 1969. – 328с.

7.           Перельман Я. И. Занимательные задачи и опыты. - Д.: ВАП, 1994. – 527с.

8.           Семеновых А. Комбинаторика //Математика. – 2004. - №15. – с. 28-32.

9.           Семеновых А. Комбинаторика //Математика. – 2004. - №16. – с. 19-22.

10.       Семеновых А. Комбинаторика //Математика. – 2004. - №17. – с. 22-27

11.       Стойлова Л. П. Математика: Учебник для студентов отделений и факультетов начальных классов средних и высших педагогических учебных заведений. - М.: Издательский центр «Академия», 1997. – 464с.

12.       Цыганов Ш. Комбинаторика от А до Я //Математика. – 2001. - №26. – с. 9-23.

13.            http://combinatorica.narod.ru/second.htm

14.             http://festival.1september.ru/articles/211057/

15.             http://www.brsu.brest.by/pages/centr_pmo/au5.html

16.             http://ro-che.info/docs/funceq.pdf

17.             http://olympiads.mccme.ru/lktg/2006/3/3-3ru.pdf

18.             http://bestbook.ru/userfiles/books/pdf/ФУ_1058.pdf