Maths Olympiad Prep

Library / /277 of 520

Combinatorics Difficulty 5.6 AIME, harder Find the answer

6. Given nn points in the plane with no three points collinear, mm line segments are drawn between these nn points. It is known that for any two points AA and BB among these nn points, there is a point CC such that CC is connected to both AA and BB by line segments. Find the minimum value of mm.

untranslated text remains the same as the source text.

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

Solution

6. Solution: Let these nn points be A1,A2,,AnA_{1}, A_{2}, \cdots, A_{n}. First, consider an example:

If nn is odd, connect the segments A1A2,A1A3,,A1An;A2A3,A4A5,,An1AnA_{1} A_{2}, A_{1} A_{3}, \cdots, A_{1} A_{n}; A_{2} A_{3}, A_{4} A_{5}, \cdots, A_{n-1} A_{n}.

If nn is even, connect the segments A1A2,A1A3,,A1An;A2A3,A4A5,,An2An1,A2AnA_{1} A_{2}, A_{1} A_{3}, \cdots, A_{1} A_{n}; A_{2} A_{3}, A_{4} A_{5}, \cdots, A_{n-2} A_{n-1}, A_{2} A_{n}.

Clearly, the segments connected by the above method satisfy the conditions, so the minimum value of mm is less than or equal to [3n22]\left[\frac{3 n-2}{2}\right]. (Note: [3n22]\left[\frac{3 n-2}{2}\right] is the number of segments connected in the above method, where [x][x] denotes the greatest integer not exceeding xx.)

Next, we prove that these nn points require at least [3n22]\left[\frac{3 n-2}{2}\right] segments to meet the requirements of the problem.

In fact, if each of A1,A2,,AnA_{1}, A_{2}, \cdots, A_{n} is connected to at least 3 segments, then m3n2>[3n22]m \geqslant \frac{3 n}{2} > \left[\frac{3 n-2}{2}\right];

If one of them (let's say A1A_{1}) is connected to no more than 2 segments, there are two cases:
(1) A1A_{1} is connected to only 1 segment, say A1A2A_{1} A_{2}, then there is no point that is connected to both A1A_{1} and A2A_{2}, which is a contradiction. Similarly, if A1A_{1} is not connected to any segment, it also leads to a contradiction.
(2) A1A_{1} is connected to exactly 2 segments, A1A2A_{1} A_{2} and A1A3A_{1} A_{3}. In this case, the segment A2A3A_{2} A_{3} must be connected (because for the two points A1A_{1} and A2A_{2}, only A3A_{3} can be connected to both A1A_{1} and A2A_{2}).

Considering the points A1A_{1} and Ai(i4)A_{i} (i \geqslant 4), AiA_{i} must be connected to either A2A_{2} or A3A_{3}. Also, from (1), AiA_{i} must be connected to at least 2 segments, so the number of segments connected from A4,A5,,AnA_{4}, A_{5}, \cdots, A_{n} (a total of n3n-3 points) is at least n3+[n22]n-3 + \left[\frac{n-2}{2}\right]. Therefore, the total number of segments connected from these nn points is at least 3+(n3)+[n22]=[3n22]3 + (n-3) + \left[\frac{n-2}{2}\right] = \left[\frac{3 n-2}{2}\right].
Thus, the minimum value of mm is [3n22]\left[\frac{3 n-2}{2}\right].

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.