Олимпиадные задачи из раздела «Статистика», «Комбинаторика», и «Теория вероятностей» Демидишина Галина Алексеевна, МБОУ «Лицей 3» - презентация

1 Олимпиадные задачи из раздела «Статистика», «Комбинаторика», и «Теория вероятностей» Демидишина Галина Алексеевна, МБОУ «Лицей 3»

2 Основные комбинаторные задачи. Основными и типичными операциями и связанными с ними задачами комбинаторики являются следующие: 1) образование упорядоченных множеств, состоящее в установлении определенного порядка следования элементов множества друг за другом, - составление перестановок; 2) образование подмножеств, состоящее в выделении из данного множества некоторой части его элементов, - составление сочетаний; 3) образование упорядоченных подмножеств - составление размещений.

3 Краткая историческая справка. Первые работы, в которых зарождались основные понятия теории вероятностей, представляли собой попытки создания теории азартных игр (Кардано, Гюйгенс, Паскаль, Ферма и другие в XVIXVII вв.). Следующий этап развития теории вероятностей связан с именем Якоба Бернулли ( ). Доказанная им теорема, получившая впоследствии название «Закона больших чисел», была первым теоретическим обоснованием накопленных ранее фактов. Дальнейшими успехами теория вероятностей обязана Муавру, Лапласу, Гауссу, Пуассону и др.

4 Основными задачами являются: · Выработка умений и навыков работать с таблицей, извлекать из таблиц информацию и анализировать ее. · Выработка умений заполнять в таблице пустые графы (строки, столбцы). · Формирование умений читать диаграммы, извлекать необходимую информацию. · Формирование умений и навыков в составлении, выборе и упорядочении комбинаторных наборов. · Формирование умений подсчета комбинаторных объектов, методом непосредственного перебора. · Показать, что такое дерево возможных вариантов, его использование как один из методов решения КЗ. · Формирование представления о том, какое событие является достоверным, какое невозможным, и какое событие мы можем назвать случайным. · Формирование у учащихся понимания степени случайности в различных событиях и явлениях и использование для ее оценки адекватных вероятностных терминов («достоверно», «маловероятно» и т.д.). Формирование комбинаторных навыков, как уже говорилось в 1 главе, нужно начинать как можно раньше. Желательно вести пропедевтическую работу уже в начальных классах.

5 Если конечные множества не пересекаются, то число элементов X U Y {или} равно сумме числа элементов множества X и числа элементов множества Y. То есть, если на первой полке стоит X книг, а на второй Y, то выбрать книгу из первой или второй полки, можно X+Y способами.

6 Если элемент X можно выбрать k способами, а элемент Y-m способами то пару (X,Y) можно выбрать k*m способами. То есть, если на первой полке стоит 5 книг, а на второй 10, то выбрать одну книгу с первой полки и одну со второй можно 5*10=50 способами.

7 Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы? Решение: X=17, Y=13 По правилу суммы X U Y=17+13=30 тем.

8 3. Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы? Решение: X=17, Y=13 По правилу суммы X U Y=17+13=30 тем. 4. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево? Решение: В таких числах последняя цифра будет такая же, как и первая, а предпоследняя - как и вторая. Третья цифра будет любой. Это можно представить в виде XYZYX, где Y и Z - любые цифры, а X - не ноль. Значит по правилу произведения количество цифр одинаково читающихся как слева направо, так и справа налево равно 9*10*10=900 вариантов.

9 Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны? Это пример задачи на размещение без повторений. Размещаются здесь 10 цифр по 6. А варианты, при которых одинаковые цифры стоят в разном порядке считаются разными. Если X-множество, состоящие из n элементов, mn, то размещением без повторений из n элементов множества X по m называется упорядоченное множество X, содержащее m элементов называется упорядоченное множество X, содержащее m элементов

10 Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневые переплеты. Сколькими способами он может это сделать? Решение: Имеется 12 книг и 3 цвета, значит по правилу произведения возможно 12 * 3 = 36 вариантов переплета.

11 Количество всех размещений из n элементов по m обозначают n! - n-факториал (factorial анг. сомножитель) произведение чисел натурального ряда от 1 до какого либо числа n n!=1*2*3*...*n0!=1 Значит, ответ на выше поставленную задачу будет Возможно вариантов

12 Также часто для наглядного решения задачи применяются круги Эйлера. Например: Из 100 туристов, отправляющихся в заграничное путешествие, немецким языком владеют 30 человек, английским - 28, французским Английским и немецким одновременно владеют 8 человек, английским и французским - 10, немецким и французским - 5, всеми тремя языками - 3. Сколько туристов не владеют ни одним языком? Из 100 туристов, отправляющихся в заграничное путешествие, немецким языком владеют 30 человек, английским - 28, французским Английским и немецким одновременно владеют 8 человек, английским и французским - 10, немецким и французским - 5, всеми тремя языками - 3. Сколько туристов не владеют ни одним языком? Всеми тремя языками владеют три туриста, значит, в общей части кругов вписываем число 3. Английским и французским языком владеют 10 человек, а 3 из них владеют еще и немецким.

13 Аналогично получаем, что только английским и немецким владеют 8-3=5 человек, а немецким и французским 5-3=2 туриста. Вносим эти данные в соответствующие части. По условию задачи всего 100 туристов =80 туристов знают хотя бы один язык, следовательно, 20 человек не владеют ни одним из данных языков. Следовательно, только английским и французским владеют 10-3=7 человек.

14 Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны? Это пример задачи на размещение без повторений. Размещаются здесь 10 цифр по 6. А варианты, при которых одинаковые цифры стоят в разном порядке считаются разными. Если X-множество, состоящие из n элементов, mn, то размещением без повторений из n элементов множества X по m называется упорядоченное множество X, содержащее m элементов называется упорядоченное множество X, содержащее m элементов.

15 Количество всех размещений из n элементов по m обозначают n! - n-факториал (factorial анг. сомножитель) произведение чисел натурального ряда от 1 до какого либо числа n n!=1*2*3*...*n0!=1 Значит, ответ на выше поставленную задачу будет Возможно вариантов

16 Задача Сколькими способами 4 юноши могут пригласить четырех из шести девушек на танец? Решение: два юноши не могут одновременно пригласить одну и ту же девушку. И варианты, при которых одни и те же девушки танцуют с разными юношами считаются, разными, поэтому: Возможно 360 вариантов.

17 В случае n=m (см. размещения без повторений) из n элементов по m называется перестановкой множества x.Количество всех перестановок из n элементов обозначают Pn.Pn=n! Действительно при n=m:

18 Сколько различных шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4,5, если цифры в числе не повторяются? Решение: 1) Найдем количество всех перестановок из этих цифр: P6=6!=720 2) 0 не может стоять впереди числа, поэтому от этого числа необходимо отнять количество перестановок, при котором 0 стоит впереди. А это P5=5!=120. P6-P5= =600

19 Квартет Проказница Мартышка Осел, Козел, Да косолапый Мишка Затеяли играть квартет … Стой, братцы стой! – Кричит Мартышка, - погодите! Как музыке идти? Ведь вы не так сидите… И так, и этак пересаживались – опять музыка на лад не идет. Тут пуще прежнего пошли у низ раздоры И споры, Кому и как сидеть…

20 Вероятно, крыловские музыканты так и не перепробовали всех возможных мест. Однако способов не так уж и много. Сколько? Здесь идет перестановка из четырех, значит, возможно P4=4!=24 варианта перестановок.

21 Сочетанием без повторений называется такое размещение, при котором порядок следования элементов не имеет значения. Всякое подмножество X состоящее из m элементов, называется сочетанием из n элементов по m. Таким образом, количество вариантов при сочетании будет меньше количества размещений. Число сочетаний из n элементов по m обозначается

22 Сколько трехкнопочных комбинаций существует на кодовом замке (все три кнопки нажимаются одновременно), если на нем всего 10 цифр. Решение: Так как кнопки нажимаются одновременно, то выбор этих трех кнопок – сочетание. Отсюда возможно вариантов.

23 У одного человека 7 книг по математике, а у второго – 9. Сколькими способами они могут обменять друг у друга две книги на две книги. Решение: Так как надо порядок следования книг не имеет значения, то выбор 2-ух книг - сочетание. Первый человек может выбрать 2 книги способами. Второй человек может выбрать 2 книги Значит всего по правилу произведения возможно 21*36=756 вариантов.

24 При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут это сделать? Решение: Первый игрок делает выбор из 28 костей. Второй из 28-7=21 костей, третий 14, а четвертый игрок забирает оставшиеся кости. Следовательно, возможно

25 Часто в задачах по комбинаторике встречаются множества, в которых какие-либо компоненты повторяются. Например: в задачах на числа – цифры. Для таких задач при размещениях используется формула, а для сочетаний.

26 Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5? Решение. Так как порядок цифр в числе существенен, цифры могут повторяться, то это будут размещения с повторениями из пяти элементов по три, а их число равно В кондитерском магазине продавались 4 сорта пирожных: эклеры, песочные, наполеоны и слоеные. Сколькими способами можно купить 7 пирожных. Решение: Покупка не зависит от того, в каком порядке укладывают купленные пирожные в коробку. Покупки будут различными, если они отличаются количеством купленных пирожных хотя бы одного сорта. Следовательно, количество различных покупок равно числу сочетаний четырех видов пирожных по семь -

27 1. Сколько перестановок можно сделать из букв слова «Миссисипи». Ответ: Имеется пять различных стульев и семь рулонов обивочной ткани различных цветов. Сколькими способами можно осуществить обивку стульев. Ответ: На памятные сувениры в «Поле Чудес» спонсоры предлагают кофеварки, утюги, телефонные аппараты, духи. Сколькими способами 9 участников игры могут получить эти сувениры? Сколькими способами могут быть выбраны 9 предметов для участников игры? Ответ: 4 9, Сколькими способами можно расставить на шахматной доске 8 ладей так, чтобы на одна из них не могла бить другую? Ответ: Сколько может быть случая выбора 2 карандашей и 3 ручек из пяти различных карандашей и шести различных ручек? Ответ: Сколько способов раздачи карт на 4 человека существует в игре «Верю не верю» (карты раздаются полностью, 36 карт). Ответ:.

28 Обезьяну посадили за пишущую машинку с 45 клавишами, определить число попыток, необходимых для того, чтобы она наверняка напечатала первую строку романа Л.Н. Толстого «Анна Каренина», если строка содержит 52 знака и повторений не будет? Решение: порядок букв имеет значение. Буквы могут повторяться. Значит, всего есть вариантов.

29 , где n-количество всех элементов, n 1,n 2,…,n r -количество одинаковых элементов. Сколькими способами можно переставить буквы слова «ананас»? Решение: всего букв 6. Из них одинаковы n 1 «а»=3, n 2 «н»=2, n 3 «с»=1. Следовательно, число различных перестановок равно.

30 1. Сколько перестановок можно сделать из букв слова «Миссисипи». Ответ: Имеется пять различных стульев и семь рулонов обивочной ткани различных цветов. Сколькими способами можно осуществить обивку стульев. Ответ: На памятные сувениры в «Поле Чудес» спонсоры предлагают кофеварки, утюги, телефонные аппараты, духи. Сколькими способами 9 участников игры могут получить эти сувениры? Сколькими способами могут быть выбраны 9 предметов для участников игры? Ответ: 4 9, Сколькими способами можно расставить на шахматной доске 8 ладей так, чтобы на одна из них не могла бить другую? Ответ: Сколько может быть случая выбора 2 карандашей и 3 ручек из пяти различных карандашей и шести различных ручек? Ответ: Сколько способов раздачи карт на 4 человека существует в игре «Верю не верю» (карты раздаются полностью, 36 карт). Ответ:.

31 1. Сколько перестановок можно сделать из букв слова «Миссисипи». Ответ: Имеется пять различных стульев и семь рулонов обивочной ткани различных цветов. Сколькими способами можно осуществить обивку стульев. Ответ: На памятные сувениры в «Поле Чудес» спонсоры предлагают кофеварки, утюги, телефонные аппараты, духи. Сколькими способами 9 участников игры могут получить эти сувениры? Сколькими способами могут быть выбраны 9 предметов для участников игры? Ответ: 4 9, Сколькими способами можно расставить на шахматной доске 8 ладей так, чтобы на одна из них не могла бить другую? Ответ: Сколько может быть случая выбора 2 карандашей и 3 ручек из пяти различных карандашей и шести различных ручек? Ответ: Сколько способов раздачи карт на 4 человека существует в игре «Верю не верю» (карты раздаются полностью, 36 карт). Ответ:.

32 1. Для дежурства в классе выделены 6 человек. Сколькими способами можно составить график? (ответ: 720) 2. Сколько различных экзаменационных комиссий можно образовать из 5 преподавателей? (ответ: 120) 3. Сколько различных перестановок можно образовать из букв слова "задача" ? (ответ: 120) 4. Сколько различных чисел можно составить из цифр 0, 1, 2, 3, 4 при условии, что в каждом из этих чисел все цифры различны? (ответ: 96) 5. Из n элементов создаются соединения по k элементов (k = n или k < n). Эти соединения отличаются друг от друга только самими элементами. Количество сочетаний можно посчитать по формуле: 6. Сколько экзаменационных комиссий, состоящих из 7 человек, можно создать их 14 преподавателей? (ответ: 3432)

33 7. При встрече 12 человек обменялись рукопожатиями. Сколько сделано рукопожатий? (ответ: 66) 8. На плоскости даны 5 точек, никакие три из них не лежат на одной прямой. Сколько прямых можно провести через эти точки? (ответ: 10) 9 Сколько диагоналей в выпуклом десятиугольнике? (ответ: 35) 10. Сколькими способами можно выбрать два карандаша и три ручки из пяти различных карандашей и пяти различных ручек? 11. Сколькими способами можно смоделировать флаг, состоящий из трех горизонтальных полос различных цветов, если имеются материал пяти различных цветов?

34 12. Десять спортсменов разыгрывают одну золотую, одну серебряную и одну бронзовую медали. Сколькими способами эти медали могут быть распределены между спортсменами? 13. На десяти одинаковых карточках написаны различные числа от 0 до 9. Определить вероятность того, что случайно составленное с помощью данных карточек двузначное число делится на Телефонный номер состоит из шести цифр, каждая из которых равновозможно принимает значения от 0 до Вычислить вероятность того, что номер не содержит цифры пять. 16. Четырехзначный номер автомобиля считается «счастливым», если сумма первых его двух чисел равна сумме двух последних. Найти вероятность встретить на улице автомобиль со «счастливым номером».