Question

In a group of nine people, one person knows exactly two others, two people know exactly 5 others, and another 2 people know exactly 6 others. Show that there are three people who all know each other

Answer 1

1, 2 and 5 all know each other.

Explanation:

I will denote the people by numbers: 1 2 3 4 5 6 7 8 9

The following information is given in the question.

1 knows two others

2 knows five others

3 knows five others

4 knows six others

5 knows six others

Let's assume the worst case: They all know different persons, so it is difficult to find three people who all know each other.

1 knows 2 and 5

2 knows 1 3 4 5 6

3 knows 9 8 7 6 2

By now, 2, 5 and 6 are known to two people, and others are known to just one person.

4 knows 9 8 7 6 5 3

5 knows 1 2 4 7 8 9

As a result 1, 2 and 5 all know each other.

1 knows 2 and 5

2 knows 1 and 5

5 knows 1 and 2

The reason for this is that there are three groups:

1, (2,3) and (4,5)

As much as we try to separate the people that they know there are nine different persons and at least three of them will be spread to these groups in common.