Maths Olympiad Prep

Library / /18 of 22

Geometry Difficulty 7.0 National olympiad, round 2 Prove it 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)

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.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.