Методические рекомендации (стр. 3 )

12) За отсутствие документов наряд милиции задержал трёх студентов разных вузов: Романа, Сергея и Павла. На допросе каждый из них показал следующее:

- Роман – я учусь в ЮрГУ, а Сергей – в ЧелГУ;

- Сергей – я учусь в ЮрГУ, а Роман – в Торговом институте;

- Павел – я учусь в ЮрГУ, а Роман – в ЧелГУ.

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

Решение: Обозначим через Ху студента, имя которого начинается с буквы Х, а у – первая буква названия института, в котором он учиться.

Т. к. в показаниях студентов одно утверждение верно, а другое – нет, то составим истинные дизъюнкции:

Рю СЧ = 1, Сю Рт = 1, ПюРч = 1.

Тогда конъюнкция этих дизъюнкций будет истинной:

Преобразуем первые двое скобок

,

,

,

.

Ответ: Сергей учится в ЧелГУ, Роман – в торговом институте, Павел – в ЮрГУ.

13) По подозрению в совершенном преступлении задержали Брауна, Джона и Смита. Один из них был уважаемым в городе стариком, другой был малоизвестным чиновником, третий – известным мошенником. В процессе следствия старик говорил правду, мошенник лгал, а третий в одном случае говорил правду, а в другом – ложь. Их утверждения следующие:

Браун: Я совершил это, Джон не виноват;

Джон: Браун не виноват. Преступление совершил Смит;

Смит: Я не виноват, виноват Браун.

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

Решение: Введём обозначения:

Б – виноват Браун, Д – виноват Джон, С – виноват Смит.

Тогда утверждения, высказанные задержанными, можно записать в виде конъюнкций:

, , , из которых по условию задачи две ложны, а одна истинна.

Тогда будет истинна.

Эта формула не тождественно истинна. Действительно, если истинно высказывание Д и ложны Б и С, то L = 0. Но эта формула не тождественно ложна. Например, при истинном высказывании Б и ложных высказываниях Д и С имеем L = 1.

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

	Б	Д	С				L
1	1	1	1	0	0	0	0
2	1	1	0	0	0	1	1
3	1	0	1	1	0	0	1
4	1	0	0	1	0	1	1
5	0	1	1	0	1	0	1
6	0	1	0	0	0	0	0
7	0	0	1	0	1	0	1
8	0	0	0	0	0	0	0

Отсюда верно, что формула L истинна в пяти случаях.

Случай 4 исключаем, т. к. оказываются истинны две конъюнкции, а это противоречит условию задачи.

В случаях 2,3,5 оказываются истинными по два высказывания Б и Д, Б и С, Д и С соответственно, что противоречит условию задачи.

Следовательно, справедлив случай 7, т. е. преступник – Смит. Он известный мошенник, и оба его высказывания ложны . При этом Б = 0, Д = 0, т. е. высказывания Б и Д ложны. Значит, истинна пара высказываний Джона, а у Брауна первое высказывание ложное, а второе – истинное. Отсюда вытекает, что Джон – уважаемый в городе старик, а Браун – малоизвестный чиновник.

14) Доказать равносильность х ~ у = .

Решение:

х ~ у =

.

III. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

БИНОМ НЬЮТОНА

Элементы комбинаторики

Определение. Различные группы, составленные из каких либо предметов и отличающихся одна от другой или порядком этих предметов, или самими предметами, называются соединениями. Предметы, из которых составлены соединения, называются элементами. Их обозначим а, в, с, … Соединения бывают трех родов: размещения, перестановки и сочетания.

1) Размещениями из элементов по называются такие соединения, из которых каждое содержит элементов, взятых из данных элементов, и которые отличаются одно от другого или элементами, или порядком элементов .

Число всевозможных размещений, которые можно составить из n элементов по m, обозначим (А начальная буква французского слова “arrangement”, что означает размещение). Тогда .

Число всевозможных размещений из n элементов по m равно произведению m последовательных целых чисел, из которых большее есть .

, и т. д.

Если ввести обозначение произведения от 1 до n через факториал (!), то , в частности .

Тогда число размещений равно .

Например, имеется 10 учебных предметов и 3 пары занятий в день. Тогда число способов составления расписания в 1 день равно: .

Пример: Сколько можно образовать целых чисел, из которых каждое изображалось бы тремя цифрами (номера машин)?

Решение: чисел.

2) Перестановками из элементов называются такие соединения, которые содержат все элементов и отличаются друг от друга только порядком элементов. Число всех перестановок из элементов обозначим через Pn ( начальная буква французского слова “permutation” что означает перестановка). Тогда

Число всех перестановок из n элементов равно произведению натуральных чисел от 1 до n.

Например, число способов размещения 12 студентов за столом, на котором поставлено 12 приборов равно: .

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

Например, из 10 кандидатов на одну и ту же должность должны быть выбраны трое. Тогда число способов выбора равно: .

Свойство сочетаний: .

Правило Паскаля: .

Ø  Принцип умножения: Пусть необходимо выполнить одно за другим, какие то действий. Если первое действие можно выполнить n1 способами, после чего второе действие можно выполнить n2 способами и т. д. до kго действия, которое можно выполнить nk способами, то все действий вместе могут быть выполнены способами.

Пример: Сколько четырехзначных чисел можно составить, используя цифры 1, 2, 3, 4, 5.

Решение:

.

Ø  Принцип сложения: Если два действия взаимно исключают одно другое, причем одно из них можно выполнить n1 способами, то какое либо одно из них можно выполнить (n1+n2) способами. Этот принцип легко обобщить на случай произвольного конечного количества действий.

Пример: В нашем распоряжении есть 3 различных флага. На флагштоке поднимается сигнал, состоящий не менее чем из 2 флагов. Сколько различных способов сигналов можно поднять на флагштоке, если порядок флагов в сигнале учитывается?

Решение: Пусть первым действием поднимем на флагшток 2 флага, а вторым действием поднимем 3 флага. По принципу умножения 2 флага можно поднять

способами. Аналогично поднять 3 флага можно способами. Мы можем поднять только один сигнал из 2 флагов, либо сигнал из 3 флагов. Эти действия взаимно исключаются, не могут быть выполнены одновременно. Тогда общее количество сигналов равно .

Ø  Перестановки с повторениями: Пусть дано множество из n элементов, в котором n1 элементов принадлежит к первому типу, n2 ко второму типу и т. д. до nk объектов kго типа, причем элементы одного и того же типа не различимы между собой. Тогда общее число перестановок данного множества элементов равно:

, где .

Пример: Сколько различных способов можно образовать из всех букв слова “Миссисипи”?

Решение: .

Ø  Размещения с повторениями: Число размещений с повторениями из элементов по задается равенством .

Ø  Сочетания с повторениями: Сочетаниями из элементов по с повторениями называются неупорядоченные выборы из предметов по с возвращениями. Число сочетаний из элементов по с повторениями равно

, можно доказать .

Примеры:

1) Упростить выражение .

Решение: .

2) Упростить выражение .

Решение: .

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

Решение: Телефонный номер обычно не начинается с “0”. Значит, вычислим число комбинаций из девяти различных цифр по 7. Это размещение.

номеров.

Если на проверку тратить 1 мин на 1 номер, то на всё уйдет 3 024 часа или 126 суток. Следователь, значит, не прав.

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

Решение: P7 = 7! = 5040 способов.

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

Решение: способами.

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

Решение: игр.

7) В телефонном номере преступника встречаются только цифры 2, 4, 5, 7 семизначного телефонного номера. Сколько всего вариантов?

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

16384 номера.

8) Сколькими способами можно разложить в ряд две зелёные и 4 красные папки?

Решение: Число способов разложения равно числу перестановок с повторениями.

способов.

9) Сколькими способами можно переставит буквы в слове “какао”, чтобы получились всевозможные различные наборы букв?

Решение: В заданном слове – 5 букв, причем “и” и “a” повторяются по два раза, а “o” встречается один раз.

Тогда способов.

10) В кондитерской имеется пять разных видов пирожных. Сколькими способами можно выбрать набор из четырёх пирожных?

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

символов.

Бином Ньютона

Это равенство называется формулой бинома Ньютона. Правая часть называется разложением бинома.

Свойства:

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

2.  Число всех членов разложения равно “m+1”, т. к. разложение содержит все степени а от 0 до m включительно.

3.  Коэффициенты равны: , где n = 0, 1, 2,…, m.

4.  Каждый член разложения можно получить из формулы

где n = 0, 1, 2, 3,…, m.

5.  Коэффициенты членов, одинаково удаленных от концов разложения, равны между собой.

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

7.  Для получения коэффициента следующего члена достаточно умножить коэффициент предыдущего члена на показатель “x” в этом члене и разделить на число членов, предшествующих определяемому.

8.  Сумма всех биномиальных коэффициентов равна 2n. Если положить в формуле бинома , то получим .

9.  Если в формуле бинома “a” заменить на “–а”, то получим: , т. е. знаки “+” и ”-” чередуются.

10.  Если в последнем равенстве положим , то получим: .

Сумма биномиальных коэффициентов, стоящих на четных местах, равна сумме биномиальных коэффициентов, стоящих на не четных местах.

Примеры:

1) Разложить по формуле бинома Ньютона: 1.; 2. .

Решение:

1.

2.

.

2) Найти 6-й член разложения (5х2 – 6а2)10.

Решение:

3) Вычислить

Решение:

.

4) В разложении вычислить член, не содержащий “x”.

Решение: .

.

, .