Ivan Treschev - Discrete Math. Practice. For students of technical specialties

Assistnt Anastasiya Sergeevna Vatolina

© Ivan Treschev, 2020

ISBN 978-5-4498-7599-0

Created with Ridero smart publishing system

This paper presents some of the tasks that can be used in preparation for the Discrete Mathematics course.

The author will be grateful for indicating shortcomings, typos, etc.

Task Problem 1: let A and B be finite sets, | A | = m, | B | = n. How many binary relations exist between A and B?

Solution: the Cartesian product will contain a total of (n*m) pairs, therefore, a total of 2 m*n subsets. Each subset is a binary relation on the set of Cartesian products, which means that there are 2 m*n relations

Problem No. 2: prove that the comparability relation modulo a positive integer n on the set Z : x = y (modn) is an equivalence relation.

Proof: non the definition of x is comparable with y modulo n if and only if x – y is divisible by n without remainder. It is an equivalence relation, since it holds:

1) Reflexivity – since x – x = 0 is divided by n , then x ≡ x ( mod n ).

2) Symmetry – if x ≡ y ( mod n ), then x – y is divided by n , then y – x is divided by n , that is, y ≡ x ( mod n ).

3) Transitivity – if x – y is divisible by n , then x – y = t 1n ( t 1 is an integer), and if y – z is divisible by n , then y – z = t 2n .

Adding these equalities, we have: x – y + y – z = t 1n + t 2n , whence x – z = ( t 1 + t 2 ) n , that is, x – z is divided by n . Thus, from x ≡ y ( mod n ) and y ≡ z ( mod n ) it follows that x ≡ z ( mod n ).

Problem No. 3: a partition of a set X is a collection of pairwise disjoint subsets of X such that each element of the set X belongs to one and only one of these subsets.

Proof: such a partition, by definition, defines the relation of belonging to a subset of the partition. Therefore, it remains to prove that this relation is equivalence.

1) reflexivity: if for any element x from X xRx performed.

2) Symmetry: Let x, y belong to the same subset, whereas

if for all x, y from X in xRy yRx follows.

3) Transitivity: If for any x,y,z X from xRy, and yRz follows xRz.

A partition of a set X is a collection of pairwise disjoint subsets of X such that each element of the set X belongs to one and only one of these subsets.

Examples.

– X= {1,2,3,4,5}. Partition: {{1,2}, {3,5}, {4}}.

– The partition of many students of the institute can be a set of groups.

In other words, a partition of a set X is a family: X= ∪ i∈IX i ∀i,j X i ⋂ X j=0,X i ⊆X is an element of the partition.

The set of equivalence classes of elements of any set of X by the equivalence relation R sets the quotient of the set X with respect R denoted and X/R. For example, a plurality of student groups of a given university is a factor in a plurality of a plurality of university students in relation to belonging to one group.

Examples.

– (x, ≤) x ≤ y (x,y) ∈ ≤ – are comparable;

– (x,y) ∉ ≤ – are not comparable.

If (x, ≤), ∀ x ∈X ∃ a ∈X| a≤x, then a is the smallest element. If ∃ a ∈X| ∀ x ∈X x≤ a, then a is the largest element.

Statement. The largest or smallest element is unique.

Evidence. Let a and b be the largest elements in (x, ≤), then ∀ x ∈X a ≥ x, in particular a ≥ b. Similar to b ≥ a, therefore a = b.

In a similar way, the statement for the smallest elements is proved.

Task number 4: in the cube with side 1, 9 points are selected. Prove that among them there are at least 2 points, the distance between which is ≤ ((√ 3) \ (2)).

Proof: break a cube into eight identical cubes with side 0.5 – according to the Dirichlet principle, at least one of these cubes will have two points.

The maximum distance between two points in a cube is equal to the size of its diagonal, i.e.0.5* √ 3.

Problem number 5: in a white sphere, 12% of its area is painted red. To prove that a parallelepiped can be entered into the sphere, in which all vertices are white.

Proof: Draw three mutually perpendicular planes through the center of the sphere and for each point of the sphere we consider its images for symmetries about these planes and for compositions of these symmetries. Each point that does not lie on these planes has exactly 8 images. Therefore, red dots and their images occupy no more than 8.12% = 96% of the area of the sphere. Therefore, there is a point for which all 8 images are white. These 8 points are the vertices of a rectangular box.

Problem number 6: prove that among any 10 integers there are several whose sum is divided by 10.

Solution: denote the numbers a 1, a 2, …, a 10. Among the numbers 0, a 1, a 1+ a 2, …, a 1+ … + a 10 there are two that have the same residues when divided by 10. Then their difference will be divided by 10.

Problem number 7: prove Bernoulli’s inequality: if x ≥ 1,then for ∀ n∈N the following holds: (1+x) n ≥ 1+nx.

Solution: we prove the inequality using the method of mathematical induction:

Base of induction: for n = 1 we have: 1+x ≥ 1+x (the inequality holds).

Induction step: let the inequality be true for k = n, we prove the inequality for k = n +1: (1+x) n+1 ≥ 1+ (n+1) x

(1+x) (1+x) n ≥ 1+nx+x (1) We use the property: if a> b and b> c, then a> c, i.e. replace: (1+x) n with (1+nx): (1+x) (1+nx) ≥ 1+nx+x

1+nx+x+nx 2 ≥ 1+nx+x

nx 2 ≥ 0 (2)

Since x 2 ≥ 0 and n ∈ N, then inequality (2) holds. Bernoulli’s inequality is proven.

Problem number 8: prove: 1+3+5+…+ (2n-1) =n 2.

Solution: we supplement the left side with even elements up to 2n, we get the arithmetic progression:

1+2+3+4+5+…+2n = ((1+2n) / (2)) *2n= (1+2n) n=n+2n 2 (1)

On the other sides we have: 1+2+3+4+5+…+ (2n-1) +2n= 1+3+5+…+ (2n-1) +2 (1+2+3+…+n)

In the second bracket we see again arithmetic progression, we get:

1+3+5+…+ (2n-1) +2 (1+2+3+…+n) = 1+3+5+…+ (2n-1) +2 ((1+n) \ (2)) n= 1+3+5+…+ (2n-1) + (1+n) n= 1+3+5+…+ (2n-1) +n+n 2 (2)

Using (1) and (2) we express 1+3+5+…+ (2n-1): 1+3+5+…+ (2n-1) = n+2n 2– (n+n 2) = n 2, as required.

This fact can also be proved using the method of mathematical induction.

Problem number 9: prove that ∀ n ∈ N the inequality holds:2 n> n.

Solution: we prove the inequality using the mathematical induction method: Induction

base: for n = 1 we have: 2> 1.

Induction step: let the inequality be valid for k = n, we prove the inequality for k = n +1: 2 n+1> n+1

2*2 n> n+1 (1) We

use the property: if a> b and b ≥ c, then a> c, i.e. we replace in (1) 2 nwith n, we have: 2n ≥ n+1

n ≥ 1 (2)

Studying inequality (2), we can conclude that 2 n> n only for n ≥ 1, and since. n ∈ N, then this condition is satisfied, the inequality is proved.