Варианты заданий

1. M= [0, 1[ ,= –1	16. M=Q,= ½
2. M= [0, 1[ ,= –2	17. M = [0, ½] ,  = –2
3. M= ]-1, 1[ ,= –1	18. M = [0, 5] ,  = –1/5
4. M= {0, 1} ,= –1	19. M = N ,  = 2
5. M = N,  = –1	20. M = R ,  = –½
6. M = R ,  = 1	21. M = Q ,  = – 1/3
7. M = [0, 1] ,  = –2	22. M = N ,  = 0
8. M = Q ,  = 2	23. M = ]–1,0] ,  = 1
9. M = R \ {1} ,  = –1	24. M = ]–1,0] ,  = 2
10. M = R ,  = 2	25. M = ]–1,0] ,  = 3/2
11. M = R ,  = ½	26. M= [0,1] ,= – 3/2
12. M = R ,  = –½	27. M= Q ,= ¾
13. M = N ,  = –2	28. M = ]–1,0] ,  = 4/3
14. M = [0, 1[ ,  = –1	29. M = R \ {1/2} ,  = –2
15. M=Q,= 0	30. M = [0, 1/3] ,  = –3

Пример решения задачи 7

Задание.Будет ли множествоM= [0,1] с операциейx*y= x+y– (9/8)xyполугруппой? Моноидом? Группой?

Решение

1) Проверим, будет ли x*yMприx,yM. Это выполнено если для всех удовлетворяющих неравенствам 0x, y1 чиселx, yбудет иметь место 0x*y1. Рассмотрим произвольный 0y1. Функцияf(x)= x+y – (9/8)xy при фиксированномyбудет линейной поx. На концах интервала [0,1] она принимает значенияf(0)=yиf(1)=1-(1/8)y. Поскольку эти значения лежат в интервале [0,1], то значения этой функции во внутренних точках интервала принадлежат [0,1]. Отсюда для всехx,yMзначенияx*yпринадлежатM.

2) Проверим ассоциативность (x*y)*z=x*(y*z). С этой целью раскроем обе части проверяемого равенства:

(x+y-(9/8)xy)+z-(9/8) (x+y-(9/8)xy)z = x+(y+z-(9/8)yz)-(9/8)x(y+z-(9/8)yz)

Поскольку последнее равенство имеет место, то операция * ассоциативна. Стало быть, (M,*) – полугруппа.

3) Проверим, будет ли (M,*) моноидом. Напомним, что моноидом называется полугруппаM, в которой существует элементeM, удовлетворяющий для всехxMсоотношениямx*e = e*x = x.

Этот элемент eMназывается нейтральным. Для нахождения нейтрального элемента получаем тождествоx+e –(9/8)xe = x , которое должно быть выполнено для всехxM. Легко видеть, чтоe=0 удовлетворяет этому тождеству. Отсюда вытекает, что (M,*) – моноид.

4) Проверим, будет ли (M,*) группой. Напомним, что моноид (M,*) называется группой, если для каждогоxMнайдется такойyM, чтоx*y = e. Отсюда данный моноид будет группой, если и только если для каждогоxMсуществуетyM, удовлетворяющий уравнениюx+y-(9/8)xy = 0. Находимy = -x/(1-(9/8)x). Отсюда дляx=8/9это уравнение не имеет решений. Стало быть, заданный моноид не является группой.

Ответ: (M,*) является полугруппой, моноидом, но не является группой.

Экзаменационные вопросы и задачи Вопросы

1. Отношения порядка и эквивалентности.

2. Сочетания и размещения.

3. Упорядоченные размещения.

4. Сочетания с повторениями .

5. Число неубывающих функций между конечными линейно упорядоченными множествами.

6. Число неубывающих сюръекций между конечными линейно упорядоченными множествами.

7. Число возрастающих отображений между конечными линейно упорядоченными множествами.

8. Применение теоремы Эйлера к классификации платоновых тел.

9. Сочетания и бином Ньютона.

10. Обобщенные биноминальные коэффициенты.

11. Решение однородных линейных рекурентных соотношений.

12. Разбиения множества и числа Стирлинга второго рода.

13. Применение эйлеровой характеристики для доказательства того, что граф K_3,3неплоский.

14. Применение эйлеровой характеристики для доказательства того, что граф K₅неплоский.

15. Число Белла.

16. Эйлерова характеристика плоских графов.

17. Принцип включения и исключения.

18. Задача о счастливых билетах.

19. Задача о встречах.

20. Производящая функция чисел Фибоначчи.

21. Теорема Эйлера о сумме валентностей вершин графа.

22. Производящая функция последовательности чисел разбиений числа.

23. Теорема о раскраске плоского графа в пять цветов.

Задачи

1. Найти все множества , удовлетворяющие условию, для некоторыхи.

2. Сколько чисел из множества {1, 2, ...., 2000} не делятся ни на 6, ни на 15, ни на 7 ?

3. Сколько подмножеств множества {1, 2, ...., 1000} содержат по крайней мере одно число кратное 6 и ни одного – кратного 15 ?

4. Найти число подмножеств множества {1, 2, …, 100}, каждое из которых либо состоит из чисел кратных 3, либо состоит из чисел кратных 4. Например {3, 12} и {4, 12} присутствуют среди этих множеств.

5. Сколько подмножеств множества {1, 2, ... , 1000} не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 7 ?

6. Из колоды, содержащей 52 карты, вытащили 10 карт. Какова вероятность того, что среди них окажется 2 туза, 2 короля и две дамы?

7. Найти производящую функцию последовательности a_n=ⁿn,n= 0, 1, 2, ... , где> 0 – действительное число.

8. Сколько ребер в полном графе K₁₀₀₀?

9. Найти число сюръекций множества {1,2,3,4,5,6,7} на множество {1,2,3}.

10. Граф состоит из двух треугольников, имеющих общую вершину. Найти хроматический многочлен этого графа.

11. Решить рекуррентное соотношение u_n+2 – 3u_n+1 + 2u_n = 0, при начальных условияхu₀ = 1, u₁ =4.

12. Найти хроматическую функцию циклического графа C₅.

13. Простой граф имеет 27 ребер. Две его вершины имеют степени 4, а остальные – степень 3. Сколько вершин имеет данный граф ?

14. Сколько разбиений множества {1,2,3,4,5,6,7} имеют в точности 4 блока?

15. Нарисовать дерево, соответствующее коду Прюфера 333221.

16. Найти производящую функцию последовательности a_n = (n+1)(n+2),

n= 0,1,2, ...

17. Из колоды, содержащей 52 карты, вытащили 10 карт. Какова вероятность того, что среди них окажется 3 туза, 2 короля и одна дама?

18. Сколько существует чисел, состоящих из невозрастающих последовательностей цифр и содержащих все цифры, например 98777665555443221110.

19. Найти производящую функцию для последовательности чисел a_n = n².

20. Сколькими способами можно представить число 3²⁰ в виде произведения четырех сомножителей? Произведения, отличающиеся перестановкой сомножителей, считать различными.

21. Нарисовать дерево, код Прюфера которого равен 555512321.

22. Найти производящую функцию последовательности a_n = n(n+1).

23. Найти производящую функцию для последовательности a_n = exp (n), где- фиксированное действительное число.

24. Сколькими способами можно представить число 1024 в виде произведения пяти сомножителей?

25. Сколько семизначных чисел, не начинающихся с нуля, не имеют одинаковых цифр?

26. Найти производящую функцию последовательности a_n = 1/(n+1).

27. Решить линейное рекуррентное уравнение u_n+2 = 4u_n+1 –4 u_n , u ₀ = 2, u₁=3.

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

29. Решить рекуррентное уравнение u_n+2 = - u_n+1 + 12 u_n , u ₀ = 2, u₁=3.

30. Сколько существует сюръекций {1,2,3,4,5,6,7}  {1,2,3,4,5} ?

31. Сколько перестановок множества {1,2,3,4,5,6} оставляют неподвижным по крайней мере 1 элемент равный 1, 2, или 3?

32. Найти число раскрасок вершин графа «буква A» в 7 цветов. Вершины, имеющие общее ребро, раскрашиваются в различные цвета.

33. Чему равна сумма делителей числа 300 ?

34. Квадрат разбит на четыре клетки. Сколькими способами можно раскрасить эти клетки, так, что любые две соседние имеют различные цвета?

35. Сколько подмножеств множества {1,2, ..., 2000} содержат по крайней мере одно число, делящееся на 6, но не содержат чисел, кратных 15?

36. Сколько существует шашечных позиций, состоящих из 5 белых и 6 черных шашек?

37. 12 человек разбились на 6 групп, по 2 человека в каждой. Сколькими способами это можно сделать?

38. Сколько существует подмножеств множества {1, 2, 3, ... , 2000} имеющих по крайней мере одно число, кратное 6 или 15.

39. Чему равна сумма делителей числа 240 ?

40. Пусть trace(A) обозначает след матрицыA. Доказать, что еслиA– матрица смежности простого графаG, то число треугольников в этом графе равноtrace(A³)/6.

41. Решить рекуррентное уравнение u_n+2= 2u_n+1-u_n, u₀=1, u₁=2.

42. Пусть A– матрица смежности простого графа (V,E). Найти число путей длины 2 между каждой парой вершин.

43. Нарисовать граф, вершинами которого являются перестановки трех элементов (i₁i₂i₃). Является ли этот граф плоским?

44. Сколько существует чисел, состоящих из 5 различных цифр и не начинающихся с 0?

45. Каждый из тридцати студентов сдал по крайней мере один зачет. Сдали зачет по математике 26 студентов, по физике – 24, по информатике – 28. Студенты, сдавшие два предмета, сдали и третий. Сколько студентов сдали все зачеты?

46. Сколько подмножеств множества {1,2,…,1000} состоят из чисел, кратных 6, но не имеют ни одного числа, кратного 15?

47. Найти сумму всех делителей числа 288.

48. Сколько различных слов можно составить с помощью перестановок слова «литература»?

49. В урне kшаров красного, зеленого и синего цвета. Какова вероятность того, что среди них 3 шара имеют красный и 2 – синий цвет.

50. Решить рекуррентное уравнение u_n+2= 10u_n+1-25u_n, u₀=1, u₁=2.