Therefore

,

Attachments: ,

meet at the same point .

link17.jpg [ 37.23 KiB | Viewed 52 times ]

3.证明(mavropnevma)Since it is irrelevant which persons of the same gender know each other, we

may assume there ore none such, and consider the bipartite graph having the left shore made of the boys and the right shore made of the girls, with an edge connecting a boy and a girl if

they know each other. The condition means

does not contain any induced

cycle of length ,

and the requirement is to show the number

of edges satisfies .

Thus it is an extremal graph theory question, for bipartite

graphs with forbidden 's; by

symmetry we should also have .

Denote by

the set of girls that each knows exactly one boy, and by

knows more than one boy;

take

and the set of girls that each and . We obviously

have

.

Let us count the number

boys, and

knows both

of objects

. For each of the

, where

is a girl, are distinct there is at most doubletons

one girl

knowing them both (by the condition), so . Moreover, by pigeonhole