Материал: Prak_alg
26
числа
y
.
Докажите
,
что
данное
отношение
является
отношением
эквива
-
лентности
.
Сколько
элементов
в
фактор
-
множестве
r
/
N
?
3.
На
R
задано
бинарное
отношение
( )
{
}
y
y
x
x
R
R
y
x
+
=
+
´
Î
=
2
2
:
,
r
.
Докажите
,
что
r
–
отношение
эквивалентности
.
Сколько
элементов
может
содержать
класс
эквивалентности
?
Существует
ли
класс
эквивалентности
,
состоящий
из
одного
элемента
?
4.
Покажите
,
что
пересечение
отношений
эквивалентности
,
опреде
-
ленных
на
некотором
множестве
A
,
является
отношением
эквивалентно
-
сти
.
5.
Докажите
,
что
если
r
–
отношение
эквивалентности
,
то
1
-
r
–
так
-
же
отношение
эквивалентности
.
6.
Какие
из
следующих
подмножеств
множества
( )
R
R
образуют
раз
-
биение
R
?
Для
каждого
разбиения
задайте
соответствующее
отношение
эквивалентности
:
1)
{
} {
}
{
}
;
0
:
,
0
:
<
Î
>
Î
x
R
x
x
R
x
2)
{
} {
} { }
{
}
;
0
,
0
:
,
0
:
<
Î
>
Î
x
R
x
x
R
x
3)
(
)
{
}
;
:
1
,
Z
Î
+
n
n
n
4)
[
]
{
}
;
:
1
,
Z
Î
+
n
n
n
5)
(
]
{
}
Z
Î
+
n
n
n
:
1
,
.
7.
Пусть
{
}
{
}
n
n
B
B
B
M
A
A
A
M
,...,
,
,
,...,
,
2
1
2
2
1
1
=
=
–
два
разбиения
множества
K
.
Докажите
,
что
множество
всех
непустых
подмножеств
вида
j
i
B
A
Ç
также
является
разбиением
множества
.
K
Какое
отношение
эк
-
вивалентности
соответствует
этому
разбиению
,
если
разбиению
1
M
соот
-
ветствует
отношение
1
r
,
а
разбиению
2
M
–
отношение
2
r
?
8.
Докажите
,
что
отношение
,
:
x y
y
делится на
x
r
N ´ N
яв
-
ляется
отношением
порядка
.
Является
ли
это
отношение
отношением
ли
-
нейного
порядка
?
Является
ли
аналогичное
отношение
отношением
поряд
-
ка
,
если
его
рассматривать
на
множестве
Z
?
9.
Докажите
,
что
отношение
( )
{
,
:
x y
x
делится на
y
или
r
=
Î ´
N N
}
x y
<
является
отношением
линейного
порядка
.
10.
На
множестве
всевозможных
разбиений
данного
множества
рас
-
смотрим
отношение
:
(
)
r
Î
2
1
,
M
M
,
если
для
любого
1
M
A
Î
существует
множество
2
M
B
Î
такое
,
что
B
A
Í
.
Докажите
,
что
рассматриваемое
от
-
ношение
является
отношением
порядка
.
Является
ли
оно
линейным
поряд
-
ком
?
11.
Перечислите
всевозможные
линейные
порядки
на
множестве
{ }
2
,
1 ,
на
множестве
{
}
3
,
2
,
1
.
Выскажите
предположение
о
числе
линейных
порядков
на
множестве
из
n
элементов
.
27
12.
Пусть
1
r
–
отношение
порядка
на
множестве
A
,
2
r
–
отношение
порядка
на
множестве
B
.
Докажите
,
что
отношение
(
) (
) (
) (
) (
)
(
)
{
}
2
2
2
1
1
1
2
1
2
1
,
,
,
:
,
,
,
r
r
j
Î
Î
´
´
´
Î
=
b
a
b
a
b
b
a
a
B
A
B
A
есть
отношение
порядка
.
13.
Для
следующего
отношения
порядка
постройте
диаграмму
Хассе
:
{
}
8
,
7
,
6
,
5
,
4
,
3
,
2
,
1
=
A
,
( )
{
}
y
x
y
x
£
´
Î
=
:
,
A
A
r
.
2.
КОМБИНАТОРИКА
2.1
Основные
правила
комбинаторики
Правило
суммы
Правило
суммы
для
двух
объектов
:
Пусть
объект
a
можно
выбрать
m
способами
,
объект
b
– n
способами
,
и
существует
k
общих
способов
вы
-
бора
объектов
a
и
b ,
тогда
один
из
объектов
«
a
или
b
»
можно
выбрать
m + n – k
способами
.
Пример
1.
Сколькими
способами
из
28
костей
домино
можно
вы
-
брать
кость
,
на
которой
есть
«2»
или
«5».
Решение
.
Выбрать
кость
,
содержащую
«2»,
можно
7-
ю
способами
,
со
-
держащую
«5» –
тоже
7-
ю
способами
,
но
среди
этих
способов
есть
один
об
-
щий
–
это
выбор
кости
«2 : 5».
В
соответствии
с
правилом
суммы
общее
чис
-
ло
способов
выбора
нужной
кости
можно
осуществить
7 + 7 – 1 = 13
спосо
-
бами
.
Правило
суммы
можно
сформулировать
для
произвольного
числа
объектов
.
Для
этого
достаточно
использовать
формулу
для
мощности
объ
-
единения
конечного
числа
множеств
.
В
случае
трёх
объектов
формула
имеет
вид
:
|A
C
B
U
U
| = |A| + |B| + |C| – |A
I
B| – |A
I
C| – |B
I
C| + |A
I
B
I
C|.
Правило
суммы
для
3-
х
объектов
:
Если
объект
а
можно
выбрать
n
1
способами
,
объект
b
–
n
2
способа
-
ми
,
объект
с
– n
3
способами
,
и
известны
n
12
общих
способов
выбора
одного
из
объектов
а
и
b
, n
13
общих
способа
выбора
одного
из
объектов
а
и
с
,
n
23
общих
способа
выбора
одного
из
объектов
b
и
с
,
а
также
известно
n
123
общих
способа
выбора
одного
их
объектов
а
, b
и
с
,
то
число
всех
способов
выбора
одного
из
объектов
«
а
или
b
или
с
»
вычисляется
по
формуле
:
n
1
+ n
2
+ n
3
– n
12
– n
13
– n
23
+ n
123.
(1)
28
Пример
2
.
В
ходе
экзаменационной
сессии
12
студентов
получили
оценки
«
отлично
», 12 – «
хорошо
», 13 – «
удовлетворительно
», 5 –
хорошо
»
и
«
отлично
», 7 – «
хорошо
»
и
«
удовлетворительно
», 8 – «
удовлетворитель
-
но
»
и
«
отлично
».
У
трех
студентов
все
виды
оценок
.
Сколько
студентов
в
группе
,
если
известно
,
что
все
они
сдали
сессию
?
Сколько
отличников
в
группе
?
Сколько
в
группе
«
чистых
»
троечников
?
Решение
.
В
условиях
задачи
n
1
=
12, n
2
=
12, n
3
=
13, n
12
= 5, n
23
= 7,
n
13
= 8, n
123
=
3.
По
формуле
(1)
находим
общее
число
студентов
в
группе
:
12 + 13 + 12 – 5 – 7 – 8 + 3 = 20;
число
отличников
в
группе
равно
:
n
1
– (n
12
+ n
13
) + n
123
= 12 – (5 + 8) + 3 = 2;
число
«
чистых
»
троечников
равно
n
3
– (n
13
+ n
23
) + n
123
= 13 – (8 + 7) + 3 = 1.
ЗАДАЧИ
И
УПРАЖНЕНИЯ
1.
Имеется
10
билетов
денежно
-
вещевой
лотереи
и
15
билетов
ху
-
дожественной
лотереи
.
Сколькими
способами
можно
выбрать
один
лоте
-
рейный
билет
?
Ответ
:
25
.
2.
Сколькими
способами
можно
подарить
сувенир
из
имеющихся
6
авторучек
, 7
репродукций
картин
и
3
альбомов
?
Ответ
:
16
.
3.
В
городе
работают
4
музея
, 3
театра
и
10
кинотеатров
.
Сколько
вариантов
для
организации
культпохода
в
воскресенье
?
Ответ
:
17
.
4.
Сколько
существует
вариантов
поездки
к
морю
,
если
туда
можно
добраться
тремя
авиарейсами
,
пятью
автодорогами
или
по
железной
дороге
?
Ответ
:
9
.
5.
Сколькими
способами
можно
купить
один
пирожок
,
если
в
продаже
7
пирожков
с
мясом
, 10
пирожков
с
повидлом
и
12
пирожков
с
капустой
?
Ответ
:
29
.
6.
В
отделе
НИИ
работают
несколько
сотрудников
,
знающих
хотя
бы
один
иностранный
язык
.
Из
них
6
человек
знают
английский
, 6 –
не
-
мецкий
, 7 –
французский
, 4 –
английский
и
немецкий
, 3 –
французский
и
немецкий
, 2 –
французский
и
английский
, 1
человек
знает
все
три
языка
.
29
Сколько
человек
работает
в
отделе
?
Сколько
из
них
знают
только
англий
-
ский
язык
?
Сколько
человек
знают
только
один
язык
?
Ответ
:
11, 1, 4
.
7.
Староста
одного
класса
дал
следующие
сведения
об
учениках
:
«
В
классе
учатся
45
человек
,
в
том
числе
25
мальчиков
; 30
учеников
учатся
на
„
хорошо
“
и
„
отлично
“,
в
том
числе
16
мальчиков
.
Спортом
занимают
c
я
28
учеников
,
в
том
числе
18
мальчиков
и
17
школьников
,
которые
учатся
на
хорошо
и
отлично
. 15
мальчиков
учатся
на
„
хорошо
“
и
„
отлично
“
и
за
-
нимаются
спортом
».
Докажите
,
что
в
этих
сведениях
есть
ошибка
.
Ответ
:
По
формуле
(1)
в
классе
47
человек
,
а
по
сведениям
старос
-
ты
– 45
.
Примечание
.
Задачи
6, 7
решить
также
с
помощью
кругов
Эйлера
.
8.
Сколько
чисел
среди
первых
100
натуральных
чисел
не
делятся
ни
на
2,
ни
на
3,
ни
на
5?
Ответ
:
74
.
Указание
.
Количество
натуральных
чисел
,
делящихся
на
m
и
не
пре
-
восходящих
a,
равно
целой
части
[ a/m ]
числа
m
a
.
9.
Сколько
чисел
среди
первых
1000
натуральных
чисел
,
не
деля
-
щихся
ни
на
3,
ни
на
4,
ни
на
5?
Ответ
:
400
.
10.
В
корзине
лежат
8
различных
яблок
и
7
различных
груш
.
Сколь
-
кими
способами
можно
взять
плод
из
корзины
?
Ответ
:
15
.
Правило
произведения
Правило
произведения
для
двух
объектов
:
Пусть
объект
a
можно
выбрать
п
способами
,
и
после
каждого
такого
выбора
объект
b
можно
выбрать
т
способами
.
Тогда
выбор
пары
«
a
и
b
»
в
указанном
порядке
можно
осуществить
n
´
т
способами
.
Пример
3.
Сколькими
способами
можно
выбрать
гласную
и
соглас
-
ную
буквы
из
букв
слова
«
студент
»?
30
Решение
.
Гласную
букву
можно
выбрать
2-
мя
способами
,
согласную
можно
выбрать
5-
ю
способами
.
По
правилу
произведения
выбор
«
гласной
и
согласной
»
можно
осуществлять
2
´
5
=
10
способами
.
Пример
4.
Сколько
существует
двузначных
четных
чисел
в
десятич
-
ной
системе
счисления
?
Решение
.
Выбираются
две
цифры
из
множества
{0,1,2,...,8,9}.
Пер
-
вая
цифра
может
быть
любой
,
кроме
нуля
.
Поэтому
ее
можно
выбрать
9-
ю
способами
.
Вторая
цифра
может
быть
любой
из
множества
{2,4,6,8,0},
ее
можно
выбрать
5-
ю
способами
.
Следовательно
,
четных
двузначных
чисел
по
правилу
произведения
будет
n
´
m = 45,
где
n = 9, m = 5.
Правило
произведения
является
следствием
теоремы
о
мощности
прямого
произведения
конечного
числа
конечных
множеств
.
В
случае
произвольного
числа
объектов
оно
формулируется
следующим
образом
:
Если
объект
a
1
можно
выбрать
п
1
способами
,
объект
a
2
– n
2
способами
,...,
объект
a
k
– n
k
способами
,
то
общее
число
полученных
таким
образом
упорядоченных
наборов
( a
1
, a
2
, … , a
k
)
можно
выбрать
n
1
´
n
2
´
…
´
n
k
способами
.
Если
требуется
выполнить
одно
за
другим
одновременно
k
действий
,
на
одно
из
которых
наложено
ограничение
,
то
подсчет
числа
возможных
комбинаций
удобнее
начинать
с
выполнения
именно
этого
действия
.
Пример
5.
В
микроавтобусе
10
мест
,
одно
из
которых
–
место
води
-
теля
.
Сколькими
способами
могут
сесть
в
автобус
10
человек
,
если
место
водителя
могут
занять
только
трое
из
них
.
Решение
.
Начнем
с
места
водителя
.
Имеется
n
1
=
3
способа
занять
его
место
.
Следующее
место
может
занять
любой
из
девяти
оставшихся
человек
,
т
.
е
. n
2
= 9
и
т
.
д
.
По
правилу
произведения
получаем
всего
воз
-
можностей
n
1
´
n
2
´
n
3
´
…
´
n
10
= 3
´
9
´
8
´
7
´
6
´
5
´
4
´
3
´
2
´
1 = 3
´
9!.
ЗАДАЧИ
И
УПРАЖНЕНИЯ
11.
Сколько
существует
двузначных
чисел
в
10-
ной
системе
счисле
-
ния
,
в
которых
нет
одинаковых
цифр
?
Ответ
:
81
.
12.
Сколько
существует
нечётных
трехзначных
чисел
?
Ответ
:
450.