Olympiad Maths Prep

Track / Stage 6 / 23 of 400 #1023 of 2000

Problem 1023

National olympiad, first round
Combinatorics Difficulty 6.0 Prove it

6.18 In a tennis club, 20 members have been scheduled for 14 singles matches, where each member participates in at least 1 match. Prove that in this arrangement, there must be 6 matches between 12 different players.

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

[Proof 1] Let the participants in the jj-th match be denoted as (aj,bj)\left(a_{j}, b_{j}\right), and define
S={(aj,bj)j=1,2,,14}. S=\left\{\left(a_{j}, b_{j}\right) \mid j=1,2, \cdots, 14\right\} .

If a subset MSM \subset S contains pairs of participants where all participants are distinct, then MM is called a "good subset" of SS. Clearly, such good subsets exist and there are only finitely many of them. Let one of the largest good subsets be M0M_{0}, with the number of its elements being rr. Clearly, it suffices to prove that r6r \geqslant 6.

Since M0M_{0} is a maximal good subset, the 202r20-2 r participants who do not appear in M0M_{0} have not played against each other. Since each participant has played at least one match, each of these 202r20-2 r participants must have played at least one match against the first 2r2 r participants. Therefore, in addition to the rr matches in M0M_{0}, there must be at least 202r20-2 r more matches, meaning the total number of matches is at least 20r20-r. Since the total number of matches is 14, we have 20r1420-r \leqslant 14, which solves to r6r \geqslant 6.
[Proof 2] Use 20 points to represent the 20 members of the club, and connect two points with a line segment if the corresponding two members have a match scheduled. Thus, we obtain a graph with 20 vertices and 14 edges.

For any vertex AA in the graph, the subgraph consisting of AA and all vertices connected to AA by a path is called a connected component. By the given information, each vertex belongs to exactly one connected component, and each connected component contains at least one edge.

Let the graph have kk connected components. Since in each connected component, the number of edges is at least the number of vertices minus 1, the total number of edges in the graph is at least the total number of vertices minus kk, i.e., 1420k14 \geqslant 20-k. Solving this, we get k6k \geqslant 6.

Taking any 6 connected components from the graph and selecting one edge from each, the 6 edges correspond to 6 matches involving 12 distinct participants.

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