Discrete Math. Practice. For students of technical specialties

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

,a

, …,a

. Among the numbers 0,a

,a

+a

, …,a

+ … +a

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)

 ≥ 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)

 ≥ 1+ (n+1) x

(1+x) (1+x)

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

 with (1+nx): (1+x) (1+nx) ≥ 1+nx+x

1+nx+x+nx

 ≥ 1+nx+x

nx

 ≥ 0 (2)

Since x

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

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

.

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

(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)

Using (1) and (2) we express 1+3+5+…+ (2n-1): 1+3+5+…+ (2n-1) = n+2n

– (n+n

) = n

, 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.