Иван Трещев – Discrete Math. Practice. For students of technical specialties (страница 2)

n ≥ 1 (2)

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

Problem number 10: prove the equality: 1²+2²+3²+…+n²= ((1) \ (6)) n (n+1) (2n+1).

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

base: for n = 1 we have: 1= ((1) \ (6)) *2*3=1

Induction step: let the inequality be valid for k = n, we prove the inequality for k = n +1: 1²+2²+3²+…+n²+ (n+1) ²= ((1) \ (6)) (n+1) (n+1+1) (2 (n+1) +1)

1²+2²+3²+…+n²+ (n+1) ²= ((1) \ (6)) (n+1) (n+2) (2n+3) (1)

Replace in (1) {1²+2²+3²+…+n²} by {((1) \ (6)) n (n+1) (2n+1)}, we get: ((1) \ (6)) n (n+1) (2n+1) + (n+1) ²= ((1) \ (6)) (n+1) (n+2) (2n+3)

n (2n+1) +6 (n+1) = (n+2) (2n+3)

2n²+n+6n+6 = 2n²+3n+4n+6

2n²+7n+6 = 2n²+7n+6

Equality is proved.

Problem number 11: there is a chessboard, a horse is located in the lower left corner. Cut the bottom right corner from the board. Question: is it possible to get around such a chessboard with a knight?

Solution: it is easy to notice that, making a move with the knight, we alternate the color of the cell on which it is located, i.e. if we started with a black cell our movement, then we must finish on white. It is also clear that the left and right lower cells are not the same color. So at the last step we have 2 cells left (a horse is standing on one of them), which we have not yet walked around, and they are of the same color.

Therefore, it is impossible to get around such a chessboard with a horse.

Problem number 12: to prove the inequality: ((1) \ (√ 1)) + ((1) \ (√ 2)) + ((1) \ (√ 3)) + ((1) \ (√ 4)) +…+ ((1) \ (√ n)) + ≥ √ n for n≥0.

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

Base of induction: for n = 1 we have:1=1.

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^-m+ ((1) \ (x^-m)) = x^m+ ((1) \ (x^m))

Let x^k+ ((1) \ (x^k)) are integers (k=0,…,k). Let us prove that x^k+1+ ((1) \ (x^k=1)) is also an integer: [(x^k+ ((1) \ (x^k))) (x+ ((1) \ (x)))] = x^k+1+ ((1) \ (x^k-1)) + x^k-1+ ((1) \ (x^k+1)) = [(x^k+1+ ((1) \ (x^k+1))) + (x^k-1+ ((1) \ (x^k-1)))] ⇒ x^k+1+ ((1) \ (x^k+1)) = (x^k+ ((1) \ (x^k))) (x+ ((1) \ (x))) – (x^k-1+ ((1) \ (x^k-1)))

The first term on the right-hand side is the product of integers by the assumption of induction, therefore, the integer, the second is similar. So, the sum is an integer, therefore, the left side is an integer.

Problem number 17: qprove that a number made up of 3ⁿ identical digits is divisible by 3ⁿ.

Proof: Fix one of the numbers – a. Denote the number made up of 3ⁿidentical digits aby A_n. We use induction on n. Obviously, A₁ is divisible by 3. Further, suppose that A_kis divisible by 3^k. Note that A_{k +1} = A_k * 100 … 0100 … 01 (the number of zeros in each ellipse is 3^k – 1). Since the sum of the digits of the number 100 … 0100 … 01 is 3, it is divided by 3, and therefore, A_{k +1}is divided by 3^k * 3 = 3^{k +1}. By induction, the statement of the problem is proved.

Problem number 18: how many ways can decompose the number 1024 into a product of three natural numbers, each of which is greater than 1.

Solution: This is the number of solutions to the equation x₁+ x₂, + x₃ = 10, where x_i> 0.

Task number 19: a group of 20 students pass tests in mathematics, physics and computer science. Many students who have passed mathematics and physics coincide with many students who have passed mathematics and computer science, and coincide with many students who have passed physics and computer science. Each student has passed at least one test. Find the number of students who have passed all tests, if they have passed mathematics 15, physics – 16, computer science – 17.

Solution: let M be the set of students who have passed mathematics; F – physics and I – computer science.

According to the inclusion and exclusion formula:

|М ∪ И ∪ Ф|= |М|+|И|+|Ф|– |М ⋂ И|– |М ⋂ Ф|– |Ф ⋂ И|+ |М ⋂ И ⋂ Ф|

|М|=15;|И|=16;|Ф|=17;

|М ∪ И ∪ Ф|=20 (Each student passed at least one test on the tap)

|М ⋂ И|= |М ⋂ Ф|= |Ф ⋂ И| ⇒ |М ⋂ И|= |М ⋂ Ф|= |Ф ⋂ И| = |М ⋂ И ⋂ Ф|;

20= 15+16+17—2 |М ⋂ И ⋂ Ф|

2 |М ⋂ И ⋂ Ф| = 15+16+17— 20

|М ⋂ И ⋂ Ф| = ((28) \ (2)) =14

So, 14 students passed all the tests.

Answer: 14 students.

Task number 20: 12 knights are sitting at the round table. From them to choose 5 which would not sit nearby.

Solution: we divide the set of all decisions into two subsets, depending on whether a particular knight is in the select team or not. Then we get: 15 +21 = 36.

Answer: 36

Problem number 21: 9 camels go in jumble. How many combinations of camel rearrangements exist, in which no camel follows the one he followed.

Solution: select the forbidden pairs: (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9). To solve, we apply the main theorem of combinatorics.

To do this, define what the object is and what the properties are. By objects we mean various arrangements of camels. In total there will be N = 9!. By properties we mean the presence of a certain pair in the permutation. Thus, the number of properties is 8. Then the number of permutations that do not have any of the 8 properties:

N (8) =9! -C₈¹*8!+ C₈²*7! -C₈³*6! + C₈⁴*5! -C₈⁵*4! + C₈⁶*3! -C₈⁷*2! + C₈⁸*1!=142729