Problem 1
给定平面上 $ 2n $ 个点，任意将 $ n $ 个点染成红色，剩下 $ n $ 个点染成蓝色。证明存在一种红蓝点的 $ 1 $-$ 1 $ 配对，使得连接它们的 $ n $ 条线段相互不相交。
证
定义红点集 $ R=\{ r_{1},r_{2},\dots,r_{n} \} $，蓝点集 $ B=\{ b_{1},b_{2},\dots,b_{n} \} $。$ R\to B $ 的映射，对应一种配对方案，总数为 $ n! $。
对于任意一种配对方案 $ \sigma $，我们定义它的总长度 $ L(\sigma) $ 为该方案中所有线段的长度之和 $$ L(\sigma) = \sum_{(r,b)\in\sigma}\text{dist}(r,b) $$ 由于总方案数有限，因此一定存在一种方案 $ \sigma_{m} $ 使得总长度 $ L(\sigma_{m}) $ 最小。我们下面证明这个最小方案中没有相交的线段。
假设在 $ \sigma_{m} $ 中存在两条线段相交，设为 $ (r_{1},b_{1}) $ 和 $ (r_{2},b_{2}) $，相交于点 $ P $。那么我们考虑交换配对变为 $ (r_{1},b_{2}) $ 和 $ (r_{2},b_{1}) $。根据三角不等式，有 $ \left| r_{1}b_{2} \right|<\left| r_{1}X \right|+\left| Xb_{2} \right|,\left| r_{2}b_{1} \right|<\left| r_{2}X \right|+\left| Xb_{1} \right| $，从而 $$ \left| r_{1}b_{2} \right| +\left| r_{2}b_{1} \right| < \left| r_{1}X \right| +\left| Xb_{1} \right| +\left| r_{2}X \right| +\left| Xb_{2} \right| = \left| r_{1}b_{1} \right| +\left| r_{2}b_{2} \right| $$ 发现交换后得到了一个总长度更小的方案，从而与总长度最小矛盾。这样我们就证明了总长度最小的配对方案所有线段必然不相交，证毕。
Problem 2
给定一个 $ n $ 个点的点集 $ V $，称一条线是好的当且仅当它恰好经过 $ V $ 中的 $ 3 $ 个点。
(1)
证明好的线段的数量至多为 $ n^{2} / 6 $。
证
由于任意两个点确定一条直线，因此任意两条不同的直线不可能共用一个点对。一条好的线段恰好包含 $ 3 $ 个点，从而恰好包含 $ 3 $ 个点对。我们设好的线段数量为 $ m $，那么一共包含了 $ 3m $ 个不同的点对。又因为点对总数为 $ \binom{ n }{ 2 } $，因此 $$ 3m \leq \binom{ n }{ 2 } \implies m \leq \dfrac{n(n-1)}{6} < \dfrac{n^{2}}{6} $$ (2)
设 $ M_{n} $ 是 $ n $ 个点所有可能的排布中最大的好的直线的数量。给出尽可能精确的 $ M_{n} $ 的下界。
解
实际上 $ M_{n} $ 的下界也是 $ \dfrac{n^{2}}{6}-O(n) $。但是由于难以构造，这里给出一个也是 $ O(n^{2}) $，为 $ \dfrac{n^{2}}{8}-O(n) $ 的构造。
我们利用三次函数来完成这个构造。构造函数 $ y=x^{3} $，取 $ x \in\{ -n, \dots,-1,0,1,\dots,n \} $ 共 $ 2n+1 $ 个点，对于每一个 $ x $，构造 $ P_{x}=(x,x^{3}) $。下面我们证明这个点集满足条件。
根据三次函数的性质，我们知道任意一条直线与它至多只有三个交点，因此不可能出现四点共线的情况。并且利用代数性质容易证明三点共线的充要条件是横坐标之和为零，也就是若 $ x,y,z\in \{ -n, \dots, n \} $ 满足 $ x+y+z=0 $，那么 $ P_{x},P_{y},P_{z} $ 共线。
在集合 $ \{ -n, \dots,n \} $ 中，不互相同的 $ x+y+z=0 $ 的组合的数量等价于满足 $ -n\leq x+y\leq n $ 的组数，从而求出总数为 $$ 3n^{2} + 3n - 6\lfloor n / 2 \rfloor $$ 由于 $ x,y,z $ 轮换，因此直线的总数为 $$ \dfrac{1}{2}n^{2} + \dfrac{1}{2}n - \lfloor n / 2 \rfloor = \dfrac{(2n+1)^{2}}{8} - O(n) $$
Problem 3
设 $ \mathcal{F} $ 为 $ [n] $ 的一个相交子集族。证明存在一个包含 $ \mathcal{F} $ 的相交子集族 $ \mathcal{F}' $，使得 $ |\mathcal{F}'| = 2^{n-1} $。
证
考虑 $ [n] $ 的所有子集，共有 $ 2^{n} $ 个。我们将这 $ 2^{n} $ 个子集分成 $ 2^{n-1} $ 对互补的集合。也就是对于任意 $ A\subseteq[n] $，它和它的补集 $ A^{c} $ 组成了一个互补对 $ \{ A,A^{c} \} $，显然 $ A $ 和 $ A^{c} $ 不相交。这说明在一个交族 $ \mathcal{F} $，它不可能同时包含 $ A $ 和 $ A^{c} $。从而说明了一个交族的大小不可能超过互补对的数量，即 $ \left| \mathcal{F} \right|\leq 2^{n}-1 $。
现在对于任意一个交族 $ \mathcal{F}\subseteq[n] $，我们进行以下操作来构造 $ \mathcal{F}' $：对于每一对互补对，如果 $ A\in \mathcal{F} $ 或者 $ A^{c}\in \mathcal{F} $，那么我们保留它们在 $ \mathcal{F}' $，否则选择 $ A $ 和 $ A^{c} $ 中的一个加入 $ \mathcal{F}' $，需要保证加入后仍然保持了交族的性质。我们证明一定可以完成构造，假设某一步中我们无论加入 $ A $ 还是 $ A^{c} $ 都会破坏交族的性质，那么
- 不能加入 $ A $ 说明 $ \mathcal{F} $ 中存在集合 $ B $ 使得 $ A\cap B=\emptyset $，从而 $ B\subseteq A^{c} $。
- 不能加入 $ A^{c} $ 说明 $ \mathcal{F} $ 中存在集合 $ C $ 使得 $ A^{c}\cap C=\emptyset $，从而 $ C\subseteq A $。 如果两个情况同时发生，那么同时存在 $ B\subseteq A^{c} $ 以及 $ C\subseteq A $，可以得到 $ B\cap C\subseteq A\cap A^{c}=\emptyset $，与 $ \mathcal{F} $ 是一个交族矛盾！
因此对于每一个互补对，我们都可以选出一个集合加入 $ \mathcal{F}' $，所以 $ \left| \mathcal{F}' \right|=2^{n-1} $，与互补对的数量相等。
Problem 4
假设我们可以将子图 $ K_{n} $ 分解为 $ m $ 个边不重叠的完全子图的并集，并且这些子图都和 $ K_{n} $ 不同，证明：$ m\geq n $。
证
我们将图 $ K_n $ 的顶点集 $ V $ 视为几何中的点集，将分解出的 $ m $ 个完全子图视为线集。我们将这个问题转化为满足 De Bruijn-Erdős 定理的结构。
对于任意两个顶点 $ u, v \in V $，它们在 $ K_n $ 中由唯一的一条边连接。由于这些完全子图构成了边的划分，该边 $ (u, v) $ 必须恰好属于某一个唯一的完全子图。这对应了平面上两个点唯一确定一条直线。
题目已知这些完全子图均不同于 $ K_n $，这意味着没有任何一个子图包含了 $ V $ 中的所有顶点，这对应了定理中要求的所有点不共线。
因此根据 De Bruijn-Erdős 定理，在线性空间中线的数量至少等于点的数量，我们就直接证明了 $ m\geq n $，证毕。