Track / Stage 5 / 370 of 400 #970 of 1964

Problem 970

AIME late

Combinatorics Difficulty 5.9 Prove it

8. In a large conference with 500 delegates, if each delegate knows 400 people, can we definitely select 6 delegates, each of whom knows each other?

Translating the text into English, keeping the original text's line breaks and format, the result is as follows:

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

8. Take 5 complete graphs $K_{100}$ , where each vertex represents a person, and two vertices are connected by an edge if the two people do not know each other. In this way, each vertex in a complete graph $K_{100}$ is connected to all other vertices in the same complete graph, but not to any vertices in the other 4 complete graphs $K_{100}$ . This means that each person knows 400 people. Since 6 representatives are selected, there must be two representatives whose corresponding vertices are in the same complete graph, meaning that there must be two representatives who do not know each other.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.