Olympiad Maths Prep

Track / Stage 6 / 106 of 400 #1106 of 2000

Problem 1106

National olympiad, first round
Combinatorics Difficulty 6.1 Prove it

【Example 10】 nn people attend the same conference. Among them, every two who do not know each other have exactly two common acquaintances, while every two acquaintances do not have any common acquaintances. Prove that each attendee has the same number of acquaintances.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Let's assume that participant A has mm acquaintances a1,a2,,ama_{1}, a_{2}, \cdots, a_{m}. Since they are all familiar with A, they do not know each other (why?). Since they do not know each other, every pair (ai,aj)\left(a_{i}, a_{j}\right), apart from A, must have another common acquaintance, and these acquaintances, of course, do not know A (why?). Furthermore, for different (ai,aj)\left(a_{i}, a_{j}\right), the other acquaintances are also different. Therefore, the number of participants who do not know A is no less than Cm2C_{m}^{2}. On the other hand, every person who does not know A has two common acquaintances with A, and since these people all know A, they must be among a1,a2,,ama_{1}, a_{2}, \cdots, a_{m}, and for different people who do not know A, the two common acquaintances (ai,aj)\left(a_{i}, a_{j}\right) will not be entirely the same (why?). Therefore, it can be concluded that the number of people who do not know A is no more than Cm2C_{m}^{2}. Combining the above, we know that the number of participants who do not know A is exactly Cm2C_{m}^{2}. Thus, the total number of participants nn should satisfy the equation
n=1+m+Cm2=1+m+12m(m+1) n=1+m+C_{m}^{2}=1+m+\frac{1}{2} m(m+1)

where 1 is A himself, mm is the number of A's acquaintances, and 12m(m1)\frac{1}{2} m(m-1) is the number of people who do not know A.

Examining this positive integer quadratic equation in mm, we find that it has only one positive root. This indicates that for each participant, the number of acquaintances mm is a constant.

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