2006 Putnam B3

Let $S$ be a finite set of points in the plane. A linear partition of $S$

is an unordered pair $\{A,B\}$ of subsets of $S$ such that $A \cup B = S$,

$A \cap B = \emptyset$, and $A$ and $B$ lie on opposite sides of some

straight line disjoint from $S$ ($A$ or $B$ may be empty). Let $L_S$ be the

number of linear partitions of $S$. For each positive integer $n$, find the

maximum of $L_S$ over all sets $S$ of $n$ points.

令 $S$ 为平面上的有限点集。 $S$ 的线性划分

是 $S$ 子集的无序对 $\{A,B\}$，使得 $A \cup B = S$，

$A \cap B = \emptyset$，并且 $A$ 和 $B$ 位于某些的相对侧

与 $S$ 不相交的直线($A$ 或 $B$ 可能为空)。设 $L_S$ 为

$S$ 的线性分区数。对于每个正整数 $n$，找到

$n$ 点的所有集合 $S$ 中的最大值 $L_S$。