Track / Stage 5 / 62 of 400 #662 of 1964

Problem 662

AIME late

Combinatorics Difficulty 5.2 Find the answer

4. There are 7 students, and it is known that each of them has at least 3 classmates among the remaining 6. Then, the number of pairs of classmates among these 7 students is $\qquad$ .

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Official solution

4.7.

Proof: 7 people are all classmates.
Take any student $A$ , according to the problem, among the remaining 6 people, there are at least 3 classmates, denoted as $A_{1} 、 A_{2} 、 A_{3}$ .

Next, we prove: the remaining 3 people $B_{1} 、 B_{2} 、 B_{3}$ are also classmates of $A$ .

If not, there must exist $B_{i}(1 \leqslant i \leqslant 3)$ who is not a classmate of $A$ , then, $A_{1} 、 A_{2} 、 A_{3}$ are also not classmates of $B_{i}$ , which means $B_{i}$ has at most 2 classmates, contradicting the condition that "each person has at least 3 classmates".
Therefore, the 7 people are all classmates.

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