A group consisting of 5 girls and 5 boys, where individuals of the same gender do not know each other, and no two girls have two mutual boy friends. What is the maximum number of acquaintances among the members of the group? How does the answer change if the group consists of 7 girls and 7 boys?
First, we show that in the case of 5 boys and 5 girls, the number of acquaintances is at most 12. Suppose this is not true, and there are at least 13 acquaintances among the members. Then, by the pigeonhole principle, there are 2 girls who together know at least 6 boys. However, they cannot know more boys, as there are only 5 boys, and they can know at most one of them together. Thus, there are 2 girls who together have 6 acquaintances, and each of them knows every boy, and one of them is known by both. In this case, however, each of the other girls can have at most 2 acquaintances, one from the above girls and one from the other boys they know, otherwise, one of them would have 2 common acquaintances. Thus, the 5 girls together have at most \(6 + 3 \cdot 2 = 12\) acquaintances, which contradicts our assumption.

In the first figure, it is shown that 12 acquaintances are possible in a way that meets the conditions. The girls are represented by the points \(L_{1}, L_{2}, \ldots, L_{5}\), and the boys by the points \(F_{1}, F_{2}, \ldots, F_{5}\). Two members of the group know each other if and only if the corresponding points are connected.

We show that in the case of 7 boys and 7 girls, the number of acquaintances is at most 21. Suppose there are more than 21. Then, by the pigeonhole principle, there is a girl who has at least 4 acquaintances. If another girl together with her knows all the boys, then the two of them together have at most 8 acquaintances, and the others, according to the reasoning used in the previous cases, can have at most 2 each, so the total number of acquaintances is at most \(8 + 5 \cdot 2 = 18\), which is a contradiction. Therefore, there is no girl who knows all the "free" boys not known by the first girl.

However, 22 acquaintances can only arise if the first girl knows exactly 4 boys, and each of the other girls knows 2 "free" boys and 1 boy from the acquaintances of the first girl. \((22 = 4 + 6 \cdot 3, 22\) more acquaintances cannot arise.) This means that among the 6 girls, there are definitely two who have a common acquaintance among the 4 boys known by the first girl (again using the pigeonhole principle, \(6 > 4\)). But these two girls also know 2 out of the 3 "free" boys, so they have a common acquaintance among the "free" boys, which contradicts the conditions of the problem. Therefore, the number of acquaintances is indeed at most 21.

That 21 acquaintances are possible is shown by the table in the second figure. The rows represent the girls, and the columns represent the boys. A 1 is written at the intersection of a row and a column if the corresponding boy and girl know each other. Dancsó Zsuzsanna (Budapest, ELTE Trefort Á. Gyak. Isk., 12th grade)

Remarks. 1. It can be shown that 21 acquaintances can only arise in a way that meets the conditions, as we have given in our example (i.e., the boys and girls can be numbered so that the acquaintances are exactly those given in the table).

2. Our problem essentially deals with two special cases of an extremal problem in graph theory. The problem is as follows:

What is the maximum number of edges a bipartite graph can have, where both vertex sets have \(n\) vertices, and it does not contain a quadrilateral?

The solution to the problem can be found, for example, on pages 334-336 of István Reiman's book "Geometry and Its Boundary Areas." Generally, it is true that the number of edges is at most \(\left(n + \sqrt{4n^3 - 3n^2}\right) / 2\), and this bound can only be achieved if there exists a finite projective plane of order \(q\), where \(n = q^2 + q + 1\).

![](https://cdn.mathpix.com/cropped/2024_05_02_01653dc5ba5c218451deg-1.jpg?height=764&width=683&top_left_y=1605&top_left_x=710)