Discrete Math. Practice. For students of technical specialties

Induction step: suppose that the inequality is true for k = n, we prove the inequality for k = n +1:

((1) \ (√ 1)) + ((1) \ (√ 2)) + ((1) \ (√ 3)) + ((1) \ (√ 4)) +…+ ((1) \ (√ n)) + ((1) \ (√ n+1)) ≥ √ n+1 (1) We

use the property: if a> b and b ≥ c, then a> c i.e. replace in (1) (((1) \ (√ 1)) + ((1) \ (√ 2)) + ((1) \ (√ 3)) + ((1) \ (√ 4)) +…+ ((1) \ (√ n))) by √ n, we have: √ n + ((1) \ (√ n+1)) ≥ √ n+1

√ n ≥ √ n+1 – ((1) \ (√ n+1))

√ n ≥ ((n+1—1) \ (√ n+1))

n ≥ ((n

) \ (n+1))

n

+n ≥ n

n ≥ 0 (2)

Studying inequality (2), we can conclude that ((1) \ (√ 1)) + ((1) \ (√ 2)) + ((1) \ (√ 3)) + ((1) \ (√ 4)) +…+ ((1) \ (√ n)) + ≥ √ n, only for n ≥ 0, which coincides with the initial conditions, the inequality is proved.

Task number 13:share the booty n robbers. Each of them has their own opinion on the value of a particular share of production, and each of them wants to get no less than (1 /n) the share of production (from their point of view). How to divide prey between robbers?

Solution: for two robbers, the task is not difficult to solve – one divides the production into two equal shares in his opinion, and the other selects the largest share from them. We will solve the problem by induction on the number of robbers, i.e. Suppose k robbers already have a way to split prey harmlessly. We will divide prey between (k +1) robbers. We divide all the prey between k robbers and then let each of them divide his share into (k +1) equal parts in his opinion. Now let the last robber select one of these parts from each of the k robbers. The last robber took (in his opinion) no less than [1 / (k +1)] the share of each of the k robbers, i.e. In total, he received at least [1 / (k +1)] from all production. Each of the first k robbers also received at least (1 / (k)) * (k / (k+1)) = (1 / (k+1)) from all production.

Problem number 14: prove that an equilateral triangle cannot be covered by two smaller equilateral triangles.

Proof: Each of the smaller triangles cannot cover more than one vertex of a large triangle. According to the Dirichlet principle, there are more cells (in this case, 3 vertices) than rabbits (2 vertices). Therefore, an equilateral triangle cannot be covered by two smaller equilateral triangles.

Problem number 15: prove that (1+x)

 ≥ 1+nx.

Proof: (1+x)

 ≥ 1+ (n+1) x

(1+x)

 (1+x) ≥ (1+nx) +x

(1+x) (1+x)

 ≥ (1+x) (1+nx) +x

(1+x) (1+nx) =1+nx+x+nx

1+nx+x ≤ 1+nx+x+nx

That is: (1+x) (1+x)

 ≥ (1+x) (1+nx) ≥ (1+nx) +x

Problem 16 if (x+ ((1) \ (x))) – an integer, whether integer x

+ ((1) \ (x)) n?

Proof: welimit the answer by induction. For n = 0: 1 +1 = 2. If n = -m, where m is the positive integer: x

+ ((1) \ (x

)) = x

+ ((1) \ (x

)) = x

+ ((1) \ (x

))

Let x

+ ((1) \ (x

)) are integers (k=0,…,k). Let us prove that x

+ ((1) \ (x

)) is also an integer: [(x

+ ((1) \ (x

))) (x+ ((1) \ (x)))] = x

+ ((1) \ (x

)) + x

+ ((1) \ (x

)) = [(x

+ ((1) \ (x

))) + (x

+ ((1) \ (x