Olympiad Maths Prep

Track / Stage 4 / 200 of 340 #460 of 2000

Problem 460

AMC 12 late, AIME early
Combinatorics Difficulty 4.9 Find the answer

1. Let SS be a set of n(n5)n(n \geqslant 5) points in the plane. If any four points chosen from SS have at least one point connected to the other three, then which of the following conclusions is correct? \qquad
(1) There is no point in SS that is connected to all other points;
(2) There is at least one point in SS that is connected to all other points;
(3) There are at most two points in SS that are not connected to all other points;
(4) There are at most two points in SS that are connected to all other points.

Official solution

-、1. (2).
In the point set SS, all points are connected to each other, which clearly satisfies the problem. Therefore, conclusions (1) and (4) are incorrect.

Suppose AA, BB, and CC are three points in the point set SS that are not connected to each other, but the remaining n3n-3 points are all connected to each other. This also clearly satisfies the problem. Hence, conclusion (3) is also incorrect.

If all points in the point set SS are connected to each other, then conclusion (2) is obviously true; otherwise, assume points PP and QQ are not connected. Take any two other points in the point set SS, say RR and TT. Among the four points PP, QQ, RR, and TT, there must be one point that is connected to the other three. This point cannot be PP or QQ, so it must be one of RR or TT (let's say RR). By the arbitrariness of points RR and TT, we know that there is at least one point in the point set SS that is connected to all other points. Therefore, conclusion (2) is correct.

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