Problem 8.4. In a class, there are 20 students. Thinking about which girls to send a Valentine's card to on February 14, each boy made a list of all the girls in the class he finds attractive (possibly an empty list). It is known that there do not exist three boys whose lists have the same number of girls. What is the minimum number of girls that can be in the class?
Answer: 6.

Solution. Let the number of girls in the class be $d$. According to the condition, there are no three boys whose lists match in the number of girls, so there can be a maximum of 2 empty lists, 2 lists with one girl, 2 lists with two girls, ..., 2 lists with $d$ girls. This means that the number of lists, and thus boys, does not exceed $2(d+1)$.

The total number of children in the class is 20 and does not exceed $2(d+1)+d=3d+2$, from which we get that $d \leqslant 6$.

It is not difficult to understand that this could happen if there were 6 girls and 14 boys in total. Two boys should have empty lists, two others should have 1 girl in their lists, another two should have 2 girls, ..., and the last two should have 6 girls (it does not matter which specific girls are in the lists, what matters is their number). In total, this results in exactly 14 lists.