we have .

On the other hand, we

have

, by Jensen's inequality.

We thus

need ,

so

.

Finally, we get

.

For equality to be reached we obviously

need , namely for each pair of boys

having exactly one girl knowing both of them; and then we need .

3.证明(crazyfehmy)Another solution: Consider the bipartite graph where there are

girls and

boys and denote the girls by

's and boys by 's as vertices.

Let denote the number of edges from the vertex

to set . If

is connected to some

and then for

any the

girl must not connected to

both

and . Now let us count such pairs. For every girl there

are many pair of edges. Since all such edge pairs must be

distinct for all girls, and since there are at most

such pairs, we have

or equivalently

Now assume that

or

. Then we have are greater than or equal

to and

are

and we need to show that

Since

for

we have

. and hence .