ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 3214
Скачиваний: 86
6
Вторая составляющая представляет собой пересечение трех мно-
жеств:
D
B
A
= {0, 1, 2, 4, 5, 8} {1, 2, 3, 4, 7, 9} {2, 8, 9} = {2}.
Точно так же находим элементы третьей составляющей множества P:
D
B
A
= {0, 1, 2, 4, 5, 8} {0, 5, 6, 8} {0, 1, 3, 4, 5, 6, 7} = {0, 5}.
Элементы последней составляющей имеют вид:
D
C
= {0, 1, 7, 8} {0, 1, 3, 4, 5, 6, 7} = {0, 1, 7}.
Объединим элементы всех четырех составляющих множества P:
P = {3, 7, 9} {2} {0, 5} {0, 1, 7} = {0, 1, 2, 3, 5, 7, 9}.
Ответ: P = {0, 1, 2, 3, 5, 7, 9}.
В ответ вводим упорядоченную по возрастанию последовательность
цифр.
Пример 2. Найдите элементы множества
D
B
D
A
C
B
A
Q
при условии, что
А = {0, 1, 5}; В = {0, 1, 2, 3};
С = {2, 3, 4, 5};
D = {1, 3, 4, 5, 7, 8}.
I = {0, 1, 2, …, 9}.
Решение. В заданном выражении Q содержатся только два множе-
ства со знаками дополнения:
A = {2, 3, 4, 6, 7, 8, 9};
B = {4, 5, 6, 7, 8, 9}.
Множество Q представляет собой объединение трех составляющих,
каждая из которых есть пересечение заданных множеств.
Находим элементы множества
C
B
A
:
C
B
A
= {0, 1, 5} {0, 1, 2, 3} {2, 3, 4, 5} = Ø.
Аналогично находим элементы множеств
D
A
и
D
B
:
D
A
= {2, 3, 4, 6, 7, 8, 9} {1, 3, 4, 5, 7, 8} = {3, 4, 7, 8}.
D
B
= {4, 5, 6, 7, 8, 9} {1, 3, 4, 5, 7, 8} = {4, 5, 7, 8}.
7
Объединив эти результаты, получаем:
Q = Ø {3, 4, 7, 8} {4, 5, 7, 8} = {3, 4, 5, 7, 8}.
Пример 3. Найдите элементы множества
D
C
C
B
A
D
B
A
Q
при условии, что
А = {1, 2, 4}; В = {1, 2, 3, 5, 6};
С = {2, 3, 4, 5, 6, 9};
D = {1, 3, 4, 6, 9}. I = {0, 1, 2, …, 9}.
Действуя как и в двух предыдущих случаях, получаем:
Q = {1, 3, 4, 5, 6, 9}.
Пример 4. Найдите элементы множества
D
C
B
D
B
D
C
A
Q
при условии, что
А = {3, 5, 8};
В = {0, 3, 6, 8};
С = {0, 3, 7, 8, 9};
D = {0, 3, 5, 8, 9}.
I = {0, 1, 2, …, 9}.
Ответ: Q = {0, 3, 5, 7, 8}.
Пример 5. Найдите элементы множества
D
C
B
D
B
A
C
A
Q
при условии, что
А = {1, 2, 3};
В = {1, 2, 4, 9};
С = {5, 7};
D = {2, 3, 4, 6, 7, 9}.
I = {0, 1, 2, …, 9}.
Ответ: Q = {4, 9}.
8
ТЕМА 2. КОМБИНАТОРИКА
Комбинаторные задачи отличаются очень большим разнообразием
по содержанию. Однако объём исходной информации, необходимой для их
решения, сравнительно невелик. Его составляют такие понятия, как факто-
риал, правило произведения, правило суммы и шесть основных формул
комбинаторики: перестановки, размещения и сочетания с повторениями
и без повторений.
В комбинаторике существуют задачи, различные по содержанию,
но имеющие одинаковые решения. Проиллюстрируем это на примере сле-
дующих трёх простейших задач:
1) Сколько существует 7-значных пятеричных чисел, состоящих
только из нечётных цифр, если в каждом числе точно три тройки?
2) Сколько четырёхбуквенных слов можно составить из букв семи-
элементного множества, если в каждом слове буквы идут в алфавитном
порядке?
3) Сколько существует двоичных чисел, в каждом из которых содер-
жится точно три нуля и точно четыре единицы?
Хотя формулировки этих трёх задач почти не имеют ничего общего,
ответ к ним один и тот же: число сочетаний из семи по три, т. е. 35.
Для правильного решения зачётной задачи необходимо иметь опре-
делённый уровень комбинаторного мышления. Чтобы его приобрести, сле-
дует разобрать решения комбинаторных задач, приведённых в учебном по-
собии. Кроме того, ниже приведено 12 задач с решениями. С ними также
полезно ознакомиться, так как задачи из контрольной работы имеют тот же
уровень сложности.
9
Пример 1. Сколько существует 6-значных чисел пятеричной систе-
мы счисления, в каждом из которых точно две одинаковые цифры,
а остальные встречаются не более чем по одному разу? Числа могут начи-
наться с нуля.
Решение. Пронумеруем разряды 6-значного числа, начиная со стар-
шего. Допустим, что в числе два нуля и они находятся слева на месте раз-
рядов 1 и 2. Тогда (в соответствии с правилом произведения) на месте тре-
тьего разряда можно поставить одну пятеричную цифру из четырёх: 1, 2, 3
или 4, на месте четвёртого – одну цифру из трёх, на месте пятого – одну
цифру из двух. Для шестого разряда осталась одна цифра. Всего таких чи-
сел 24.
Нули могут занимать другие места в шестизначном числе, например
первое и пятое, второе и четвёртое и т. д. Всего существует
15
2
6
C
спосо-
бов занять двумя нулями два места из шести. Каждому из этих способов со-
ответствует 24 искомых числа. Следовательно, существует 24
15 = 360 чи-
сел, содержащих по два нуля.
Повторяться могут не только нули, но и остальные цифры. Тогда по-
лучим 360
5 = 1800 чисел.
Ответ: 1800.
Пример 2. Сколько существует 4-значных шестеричных чисел, каж-
дое из которых начинается с цифры, являющейся простым числом, и окан-
чивается цифрой, делящейся без остатка на 2, если на повторы цифр огра-
ничений нет?
Решение. Пронумеруем слева направо разряды числа. На первое ме-
сто можно поставить одну цифру из трёх: 2, 3, 5. На месте второго разряда
можно поставить одну цифру из шести, так как ограничений на повторы
нет. То же самое относится и к третьему разряду. Оканчиваться число может
10
только чётной цифрой: 0, 2, 4. Таким образом, всего существует 3
6 6 3 =
= 324 искомых числа.
Ответ: 324.
Пример 3. Сколько существует 4-значных пятеричных чисел, в каж-
дом из которых нет единиц, вторая и третья цифры совпадают, а на выбор
остальных цифр ограничений нет? Повторы цифр возможны. Числа могут
начинаться с нуля.
Решение. Пронумеруем разряды числа, начиная со старшего.
На первом месте может стоять одна цифра из четырёх (так как единица
из цифр удалена), на втором – также одна из четырёх. Для третьей цифры
выбора нет: она должна повторить предыдущую – один вариант. Оканчи-
ваться число может одной цифрой из четырёх. Следовательно, всего иско-
мых чисел существует:
4
4 1 4 = 64.
Ответ: 64.
Пример 4. Сколько существует 3-значных десятичных чисел, в кото-
рых каждая следующая цифра на три меньше предыдущей и каждое из чи-
сел оканчивается чётной цифрой?
Решение. Если цифра младшего разряда – нуль, то слева от неё – 3,
а левее тройки – 6. Получили одно число: 630. Если цифра младшего раз-
ряда – единица, то слева от неё – 4, а левее четвёрки – 7. Получили второе
число 741. Каждая его цифра на единицу больше соответствующих цифр
числа 630. Аналогично получаем ещё два числа: 852 и 963. Из этих четы-
рёх чисел два числа оканчиваются чётной цифрой.
Ответ: 2.