Discrete Math. Practice. For students of technical specialties

)))] ⇒ x

+ ((1) \ (x

)) = (x

+ ((1) \ (x

))) (x+ ((1) \ (x))) – (x

+ ((1) \ (x

)))

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

. We use induction on n. Obviously, A

 is divisible by 3. Further, suppose that A

is divisible by 3

. Note that A

 = A

 * 100 … 0100 … 01 (the number of zeros in each ellipse is 3

 – 1). Since the sum of the digits of the number 100 … 0100 … 01 is 3, it is divided by 3, and therefore, A

is divided by 3

 * 3 = 3

. 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

> 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