a connected social network
Source: Saint Petersburg MO 2020 Grade 10 Problem 6
May 7, 2020
combinatorics
Problem Statement
On a social network, no user has more than ten friends ( the state "friendship" is symmetrical). The network is connected: if, upon learning interesting news a user starts sending it to its friends, and these friends to their own friends and so on, then at the end, all users hear about the news.
Prove that the network administration can divide users into groups so that the following conditions are met:[*] each user is in exactly one group
[*] each group is connected in the above sense
[*] one of the groups contains from to members and the remaining from to .