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

((2) \ (3)) – ((2) \ (3)) * ((-1) \ (2)) ⁿ

      Answer: u_n= ((2) \ (3)) – ((2) \ (3)) * ((-1) \ (2)) ⁿ

      Task number 32: 15 students shook hands at a meeting of students, three people made 4 handshakes, and others – 3. How many students were there.

      Solution: We will consider a case requiring a smaller number of participants. Since the three made 4 handshakes: we consider. That between them they made maximum handshakes – two, and formed a complete 3x vertex graph and used only 3 handshakes out of the total:

      Each «had» two handshakes. The minimum number of vertices that must be added so that the condition «three made 4 handshakes» is met – these are two. Let’s portray them like this:

      We get already 9 used handshakes. And the two added vertices have 3 handshakes, which corresponds to the condition. It remains 6. Just the full 4-vertex graph gives us 6 handshakes for each of the 4 students added: