4 A class has 30 students, all of different ages, and each student has the same number of friends within the class. For a student , if is older than more than half (not including half) of 's friends, then is called elderly. What is the maximum number of elderly students? (20th All-Russian Mathematical Olympiad
Solution
4. Suppose there are older students, each of whom has friends. For the convenience of describing the problem, use 30 points to represent 30 students. For any two points and , if and are friends, and is older than , then draw a directed edge pointing to , resulting in a tournament graph. The points corresponding to older students are called "large points", and all the large points are denoted as . According to the problem, , , thus . Without loss of generality, assume the age of the age of the age of , then (point can draw edges to at most points outside of ), . Calculate the sum of the out-degrees of all "large points". On one hand, . On the other hand, , so , thus (1). Additionally, , so (2). By eliminating from (1) and (2) (using the monotonicity of the function on the right side of (1) with respect to ), we have , which simplifies to (3). However, , and the largest integer that satisfies (3) is . Therefore, the number of older students is no more than 25. Finally, is possible. In fact, when , the above inequalities hold with equality, substituting into (2), we solve to get .
Arrange into 6 rows (as shown in the figure),
specifying that and are a pair of friends if and only if and satisfy one of the following 3 conditions:
(1) and are in adjacent rows but different columns.
(2) and are in the same column, but one of them is in the last row.
(3) and are both in the first row.
\begin{tabular}{rrrrr}
1, & 2, & 3, & 4, & 5 \\
6, & 7, & 8, & 9, & 10 \\
11, & 12, & 13, & 14, & 15 \\
16, & 17, & 18, & 19, & 20 \\
21, & 22, & 23, & 24, & 25 \\
26, & 27, & 28, & 29, & 30
\end{tabular}
In this case, each person has 9 friends. For example, the 9 friends of 1 are , and 26. Therefore, the maximum value of is 25.