## Task 2.

A cut of a finite set of points in the plane is a partition of this set into disjoint subsets $A$ and $B$, for which there exists a line that does not pass through any point of the observed set, such that all points of set $A$ are on one side, and all points of set $B$ are on the other side of this line. Determine the maximum possible number of cuts of a set of $n$ points in the plane.
## Solution.

Let the number of partitions of a set of $n$ points in the plane be at most $a_{n}$.

Consider a set $\mathcal{S}$ of $n+1$ points in the plane and note one point on the convex hull of this set, call it $T$. Observe that each partition of $\mathcal{S}$ restricts to a partition of $\mathcal{S} \backslash\{T\}$ by ignoring the point $T$. Let $\{A, B\}$ and $\{C, D\}$ be two different partitions of the set $\mathcal{S}$ that restrict to the same partition of the set $\mathcal{S} \backslash\{T\}$. This means that $\{A \backslash\{T\}, B \backslash\{T\}\}=\{C \backslash\{T\}, D \backslash\{T\}\}$. Furthermore, this means that, without loss of generality, the sets $A$ and $C$ coincide, as do the sets $B$ and $D$, except for the point $T$. However, this then means that for the partition $\{A \backslash\{T\}, B \backslash\{T\}\}$ of the set $\mathcal{S} \backslash\{T\}$, we can take a line passing through the point $T$ such that all points of the set $A \backslash\{T\}$ are on one side of this line, and all points of the set $B \backslash\{T\}$ are on the other side.

Consider all lines in the plane that pass through the point $T$ and do not pass through any point of the set $\mathcal{S} \backslash\{T\}$. Two such lines can give different partitions of the set $\mathcal{S} \backslash\{T\}$ only if there is at least one point of the set $\mathcal{S} \backslash\{T\}$ between them. Therefore, the number of different partitions of the set $\mathcal{S} \backslash\{T\}$ corresponding to some line through $T$ is at most $n$, i.e., as many as there are points in the set $\mathcal{S} \backslash\{T\}$.

Finally, we see that

$$
a_{n+1} \leqslant n+a_{n} \leqslant n+(n-1)+a_{n-1} \leqslant \cdots \leqslant n+(n-1)+\cdots+2+1+a_{1}=\binom{n+1}{2}+1
$$

Thus, a set of $n$ points in the plane can have at most $\binom{n}{2}+1$ partitions. This number is achieved, for example, by a regular $n$-gon.