Maths Olympiad Prep

Track / Stage 7 / 41 of 300 #1921 of 2444

Problem 1921

National Olympiad second round; IMO P1/P4
Geometry Difficulty 7.0 Prove it Croatian Mathematical Olympiad · Croatia

A section of a finite set of points in the plane is a partition of that set into disjoint subsets AA and BB, such that there is a line not passing through any of the points in the set so that all the points of the set AA are on one side of the line, and all the points of the set BB are on the other. Determine the maximum possible number of sections of a set of nn points in the plane. (Putnam 2006)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Let ana_n be the maximum possible number of sections of a set of nn points in the plane.
Let SS be a set of n+1n+1 points in the plane and let us consider one of these points, call it TT, on the convex hull of that set. Note that each section of SS restricts to a section of the set S{T}S \setminus \{T\}. Let {A,B}\{A, B\} and {C,D}\{C, D\} be two different sections of the set SS that restrict to the same section of the set S{T}S \setminus \{T\}. This means that {A{T},B{T}}={C{T},D{T}}\{A \setminus \{T\}, B \setminus \{T\}\} = \{C \setminus \{T\}, D \setminus \{T\}\}. Furthermore, it means, without loss of generality, that the sets AA and CC are the same and the sets BB and DD are the same, up to the point TT. Hence, for the section {A{T},B{T}}\{A \setminus \{T\}, B \setminus \{T\}\} of the set S{T}S \setminus \{T\} we can take a line passing through the point TT such that all the points of the set A{T}A \setminus \{T\} are on one side of the line, while all the points of the set B{T}B \setminus \{T\} are on the other.
Let us consider all the lines passing through the point TT and none of the points of the set S{T}S \setminus \{T\}. Two such lines could give two different sections of the set S{T}S \setminus \{T\} only if there is at least one point of the set S{T}S \setminus \{T\} between them. Hence, the number of different sections of the set S{T}S \setminus \{T\} corresponding to a line passing through TT is at most nn, i.e. as many as there are points in the set S{T}S \setminus \{T\}.
Finally, we note that
an+1n+ann+(n1)+an1n+(n1)++2+1+a1=(n+12)+1. a_{n+1} \le n + a_n \le n + (n-1) + a_{n-1} \le \dots \le n + (n-1) + \dots + 2 + 1 + a_1 = \binom{n+1}{2} + 1.
So, the set of nn points in the plane can have at most (n2)+1\binom{n}{2} + 1 sections. That number is achievable, e.g. in the case of a regular nn-gon.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.