Maths Olympiad Prep

Library / /263 of 520

Combinatorics Difficulty 5.2 AIME, harder Find the answer

Example 5. (Hefei Mathematical Competition Question in 1983) A new station is opened, and several bus routes are planned to serve the community. Their wishes are: (1) to open as many routes as possible; (2) each route must have at least one bus stop; (3) ensure that each bus stop is served by at least two different routes. Under these conditions, what is the maximum number of routes they can open? How many stops should each route have at minimum?

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

Solution

Let SS be the number of lines that can be opened, and consider the lines as vertices to form a graph KsK_{\mathrm{s}}. Label the 1983 stations as A1,A2,,A19A_{1}, A_{2}, \cdots, A_{19}. If two lines have a common station, color the edge between the corresponding two vertices with color CC.
From (2), every edge of KsK_{\mathrm{s}} can be colored;
and (3), the number of different colors used on any two different edges of KsK_{\mathrm{s}} is
12S(S1)1983 \frac{1}{2} S(S-1) \leqslant 1983 \text {. }

From (1), SS can only be 63. From the above solution process, it is easy to see that at most 63 lines can be opened; and because each vertex of K:3K_{:} 3 is connected to 62 edges of different colors, each line must pass through at least 62 stations.

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.