Maths Olympiad Prep

Library / /211 of 520

Combinatorics Difficulty 6.4 National olympiad Find the answer

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 AA, if AA is older than more than half (not including half) of AA's friends, then AA is called elderly. What is the maximum number of elderly students? (20th All-Russian Mathematical Olympiad

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

Solution

4. Suppose there are tt older students, each of whom has kk friends. For the convenience of describing the problem, use 30 points to represent 30 students. For any two points AA and BB, if AA and BB are friends, and AA is older than BB, then draw a directed edge pointing to BB, resulting in a tournament graph. The points corresponding to older students are called "large points", and all the large points are denoted as A1,A2,,AtA_{1}, A_{2}, \cdots, A_{t}. According to the problem, d+(Ai)>d(Ai)d^{+}\left(A_{i}\right) > d^{-}\left(A_{i}\right), d(Ai)=d+(Ai)+d(Ai)=kd\left(A_{i}\right) = d^{+}\left(A_{i}\right) + d^{-}\left(A_{i}\right) = k, thus d+(Ai)k+12d^{+}\left(A_{i}\right) \geqslant \frac{k+1}{2}. Without loss of generality, assume the age of A1A_{1} \leqslant the age of A2A_{2} \leqslant \cdots \leqslant the age of AtA_{t}, then d+(A1)30td^{+}\left(A_{1}\right) \leqslant 30-t (point A1A_{1} can draw edges to at most 30t30-t points outside of A1,A2,,AtA_{1}, A_{2}, \cdots, A_{t}), d+(At)=kd^{+}\left(A_{t}\right) = k. Calculate the sum SS of the out-degrees of all "large points". On one hand, S=d+(A1)+d+(A2)++d+(At1)+kk+12(t1)+kS = d^{+}\left(A_{1}\right) + d^{+}\left(A_{2}\right) + \cdots + d^{+}\left(A_{t-1}\right) + k \geqslant \frac{k+1}{2}(t-1) + k. On the other hand, SG=15kS \leqslant \|G\| = 15k, so 15k=GSk+12(t1)+k15k = \|G\| \geqslant S \geqslant \frac{k+1}{2}(t-1) + k, thus t28kk+1+1t \leqslant \frac{28k}{k+1} + 1 (1). Additionally, k+12d+(A1)30t\frac{k+1}{2} \leqslant d^{+}\left(A_{1}\right) \leqslant 30-t, so k592tk \leqslant 59 - 2t (2). By eliminating kk from (1) and (2) (using the monotonicity of the function on the right side of (1) with respect to kk), we have t28(592t)602t+1t \leqslant \frac{28(59-2t)}{60-2t} + 1, which simplifies to t259t+8560t^2 - 59t + 856 \geqslant 0 (3). However, t30t \leqslant 30, and the largest integer tt that satisfies (3) is t=25t = 25. Therefore, the number of older students is no more than 25. Finally, t=25t = 25 is possible. In fact, when t=25t = 25, the above inequalities hold with equality, substituting into (2), we solve to get k=9k = 9.

Arrange 1,2,,301, 2, \cdots, 30 into 6 rows (as shown in the figure),
specifying that ii and jj are a pair of friends if and only if ii and jj satisfy one of the following 3 conditions:
(1) ii and jj are in adjacent rows but different columns.
(2) ii and jj are in the same column, but one of them is in the last row.
(3) ii and jj 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 2,3,4,5,7,8,9,102, 3, 4, 5, 7, 8, 9, 10, and 26. Therefore, the maximum value of tt is 25.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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