The right translation (I read the official solution) would be "there are 100 children who refuse to change their clothes". They are not the children who cannot change while preserving the property. (So, the translator's comment after "100 children" seems wrong ) Let $V_1, V_2, ... , V_7$ be the set of children with each colors. Define $G_{i,j}$ as the graph with vertex $V_i \cup V_j$ with two vertex connected with edge if and only if there are friend. Let $c_{i,j}$ be the number of the connected components of $G_{i,j}$. If $c_{i,j}$ is greater than $100$ for some $i<j$, one of the component does not contains the '100 children'. Thus, we can let children with cloth $i$ to $j$, and $j$ to $i$ and still friends wear different clothes. Assume $c_{i,j} \le 100$ for every $i<j$. Then the number of edge of $G_{i,j}$ is at least $|V_i |+|V_j | - c_{i,j}$. If we sum over every $i<j$, total number of edge is at least $6 \times (|V_1 |+...+|V_7 |)- \sum c_{i,j} \ge 60000-2100>55000$. However, the total number of edges are $55000$ since each child has 11 friends. Therefore, $c_{i,j}>100$ for some $i<j$ and we can always find some children not containing the "100 children" who can change their clothes preserving the property.

bumjoooon wrote: Assume $c_{i,j} \le 100$ for every $i<j$. Then the number of edge of $G_{i,j}$ is at least $|V_i |+|V_j | - c_{i,j}$. . As far as I understand, the number of edge of $G_{i,j}$ is equal to $c_{i,j}$. bumjoooon wrote: Therefore, $c_{i,j}>100$ for some $i<j$ and we can always find some children not containing the "100 children" who can change their clothes preserving the property. Why the exchanging preserves the property? For example: A(red)<-friend->B(green)<-friend->C(red). When B exchanges a shirt to A. B and C violate the property. I really don't understand this problem

CaptainCuong wrote: bumjoooon wrote: Assume $c_{i,j} \le 100$ for every $i<j$. Then the number of edge of $G_{i,j}$ is at least $|V_i |+|V_j | - c_{i,j}$. . As far as I understand, the number of edge of $G_{i,j}$ is equal to $c_{i,j}$. bumjoooon wrote: Therefore, $c_{i,j}>100$ for some $i<j$ and we can always find some children not containing the "100 children" who can change their clothes preserving the property. Why the exchanging preserves the property? For example: A(red)<-friend->B(green)<-friend->C(red). When B exchanges a shirt to A. B and C violate the property. I really don't understand this problem Oh, it seems like the translation had mislead you. Each children do not need to change shirt with their friend. Each student has the closet with fulled with each colour. So in your case A(red) - B(green) - C(red) become A(green) - B(red) - C(green).