# Adaptation course in Discrete Math (факультатив)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

## General Information

The main goal of the Discrete Mathematics Adaptation Course is to help students keep up with the course curriculum by discussing the most important and challenging topics in detail. The second very important goal of the course is to teach students to work competently with mathematical definitions and proofs, correctly logically build solutions to problems and prove statements. The topics of the course are coordinated with the "basic" course of the DSBA and SE program, but its study will also be useful for the direction of AMI. The approximate order of topics is sets and logic, functions and relations, the beginning of number theory, combinatorics, graphs, the foundations of probability theory, generating functions.

## Schedule

The classes are organised on Saturdays at 16:20.

## Course materials

First semester

Date Topic Problem Set Class note Video
21.09.22 Statements, connectives, quantifiers Problem Set 1 -
28.09.22 Validity of statements, types of proof Problem Set 2 Solutions -
7.10.22 Three types of mathematical induction Problem Set 3 Solutions Video 3
14.10.22 Proofs with induction Problem Set 4 Solutions -
21.10.22 Divisibility. Calculation of remainders. Direct proofs. Problem Set 5 Solutions
11.11.22 Great commod divider, the main thorem of arithmetic, direct proofs. Problem Set 6 Solutions
19.11.22 Fermat's Little theorem, inverse elements in groups \$\mathbb{Z}_p\$, congruences. Problem Set 7 Solutions
25.11.22 Fermat's Little theorem, inverse elements in groups \$\mathbb{Z}_p\$, congruences. Problem Set 8 Solutions

[ -]

2.12.22 Application of Euler's theorem and Euclidean algorithm, cryptography Problem Set 9 Solutions
9.12.22 Sets, direct proofs of set identities Problem Set 10 Solutions Video 10
16.12.22 Operations with sets, cardinality and power set Problem Set 11 Solutions
21.01.23 Sets once again, proofs that a statement is wrong Problem Set 12 Solutions
28.01.23 Relations, main definitions Problem Set 13 Solutions

[ Video 13]

11.02.23 Relations, proofs of inclisions and construction of counterexamples. Problem Set 14 Solutions
17.02.23 Functions and their properties. Problem Set 15 [Solutions]

[ Video 15]

## Homeworks

Homework 1 (Logics), Deadline 31st October

Homework 2 (Induction), Deadline 31st November, better to complete before the November Test

Hint🦉 in Problem 5: Do not try to prove P(n) out of P(n-1). Assume that P(1), P(2), ...P(n-1) are all true. For proving P(n) say: lets find the biggest Fibonacci number F_i<n. Then, n = F_i + k. For the k apply your assumption😉😉

Homework 3: write down solutions to exam 1 in a perfect manner (like you you are going to print a book of your solutions), Deadline 25th November. You can pass them written or orally on Fridays evenings. Do it if you want to have MAX in the retake(if so happened) and in the exam in the end of the course.

Homework 4 (Number theory), Deadline with bonus 29th December

## References

1. Discrete Mathematics (An Open Introduction) by Oscar Levin, p. 197 Logics. Many simple problems with solution to feel the topic.

PLUS: there is a folder with records on wikipage

3. Шень А., Математическая индукция. 5-е изд, М.: МЦНМО, 2016. Many problems to work with three different versions of induction.