Maths Olympiad Prep

Track / Stage 5 / 72 of 400 #672 of 1964

Problem 672

AIME late
Combinatorics Difficulty 5.2 Find the answer

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 .

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Next problem →

Official solution

4.7.

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

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

If not, there must exist Bi(1i3)B_{i}(1 \leqslant i \leqslant 3) who is not a classmate of AA, then, A1A2A3A_{1} 、 A_{2} 、 A_{3} are also not classmates of BiB_{i}, which means BiB_{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 reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.