Problem 1 设 $ H = (V, \mathcal{F}) $ 是一个没有孤立点的超图，满足每条超边至少包含 3 个顶点，且任意两条超边恰好共享一个顶点。假设 $ H $ 不是 2-可着色的（即不能用两种颜色对顶点染色使得每条超边内都有不同颜色的点）。 (1) 证明每个顶点 $ v $ 至少属于 $ \mathcal{F} $ 中的两条超边。 证 假设存在一个顶点 $ v $ 满足 $ d(v)< 2 $。由于没有孤立顶点，因此 $ d(v)=1 $，恰好属于一条超边，记为 $ E $。 我们将顶点 $ v $ 染成红色，将 $ E $ 中的其他点染成蓝色，再将图中除了 $ E $ 之外的所有点染成红色。由于任意两条超边恰好共享一个顶点，并且 $ v $ 只在 $ E $ 中，所以任意一条超边必然和 $ E $ 存在蓝色交点，存在颜色不同的点。因此我们就构造出了一个合法的 2-着色方案，与题设矛盾。 因此每个顶点至少属于两条超边。证毕。 ...
Problem 1 假设有 $ m $ 个俱乐部和 $ n $ 个人，满足以下条件： (i) 每个俱乐部的人数为偶数； (ii) 任意两个俱乐部之间共同拥有的人数为奇数。 证明：$ m \le n $。 证： 我们在有限域 $ \mathbb{F}_{2} $ 上考虑。设 $ v_{1},\dots,v_{m}\in \mathbb{F}_{2}^{n} $ 为每个俱乐部对应向量。根据条件，我们知道 人数为偶数：$ v_{i}\cdot v_{i}=0 $ 交集为奇数：$ v_{i}\cdot v_{j}=1(i\neq j) $ 考察这 $ m $ 个向量的线性相关性。假设存在系数 $ c_{1},\dots c_{m}\in \mathbb{F}_{2} $ 使得 $$ \sum_{i=1}^{m} c_{i}v_{i}=\mathbf{0} $$ 那么对于任意 $ j\in [m] $，我们将上式与 $ v_{j} $ 做内积 $$ \left( \sum_{i=1}^{m} c_{i}v_{i} \right)\cdot v_{j} = c_{j}(v_{j}\cdot v_{j}) + \sum_{i\neq j}c_{i}(v_{i}\cdot v_{j}) = 0 $$ 带入得到 $$ \sum_{i\neq j}c_{i}=0 $$ 由于对于每个 $ j $ 这个条件都要成立，从而 $ c_{j}=\sum_{i\in[m]}c_{i} $，这意味着所有的 $ c_{i} $ 都相等，因此要么全为 $ 0 $，要么全为 $ 1 $。若全为 $ 0 $，则线性无关；若全为 $ 1 $，显然与 $ \sum_{i\neq j}c_{i}=0 $ 矛盾。 ...
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 1 设 $ n>rst $。证明 $ n $ 个数的实数列一定至少含有长度为 $ r $ 的严格上升子序列、长度为 $ s $ 的严格下降子序列、长度为 $ t $ 的常数列中的一个。 证 反证法，假设结论不成立。 我们为第 $ i $ 个元素 $ x_{i} $ 记下标签 $ (a_{i},b_{i}) $，其中 $ a_{i} $ 表示以 $ x_{i} $ 结尾的最长上升子序列长度，$ b_{i} $ 表示以 $ x_{i} $ 结尾的最长下降子序列长度。那么我们有 $ a_{i}\in[r-1],b_{i}\in[s-1] $。因此总共只有 $ (r-1)(s-1) $ 种标签，此时又有 $ n>t\cdot(r-1)(s-1) $，所以至少有 $ t $ 个元素的标签完全相同。 我们假设 $ a_{i}=a_{j},b_{i}=b_{j} $，可以证明 $ x_{i}=x_{j} $。如果不相等，不妨设 $ i< j $。若 $ x_{i}< x_{j} $，那么我们将 $ x_{j} $ 加到以 $ x_{i} $ 结尾的最长上升子序列之后，就得到了一个长度为 $ a_{i}+1 $ 的上升子序列，所以 $ a_{j}\geq a_{i}+1 $，与 $ a_{i}=a_{j} $ 矛盾；若 $ x_{i}>x_{j} $，同理可以得到 $ b_{j}\geq b_{i}+1 $，与 $ b_{i}=b_{j} $ 矛盾。所以一定有 $ x_{i}=x_{j} $。 ...
Problem 1 在一个 $ m $ 条边的二分图中，存在一个匹配，其大小至少为 $ m / \Delta $，其中 $ \Delta $ 表示图中最大顶点的度数。 证 我们需要证明这个二分图最大匹配的大小大于等于 $ m / \Delta $。根据柯尼希定理，只需要证明最小边覆盖的大小大于等于 $ m / \Delta $。 设最小边覆盖大小为 $ t $。若 $ t< m / \Delta $，对于一个被选中的顶点 $ v $，其至多覆盖 $ \text{deg}(v)\leq\Delta $ 条边，因此最多只能覆盖 $$ t\cdot\Delta < m $$ 显然不能覆盖所有的边，不可能是一个边覆盖，矛盾。 因此至少存在一个匹配的大小至少为 $ m / \Delta $。 Problem 2 证明一名学生有 $ 20 $ 周的时间来准备 ICPC，他决定每周至少完成一次训练比赛，但他只有 $ 30 $ 套训练题。请证明，无论他如何安排训练，都会存在连续的几周，他完成的训练题集数正好是 $ 9 $ 套。 ...
Problem 1 (1) 证明： $$ \chi(G) + \chi(\overline{G}) \leq v(G) + 1 $$ 证 归纳证明。对于大小为 $ 1 $ 的图，结论显然成立，此时 $ \chi(G)=\chi(\overline{G})=1 $。 假设对于大小为 $ n-1 $ 的图这个结论都成立，那么对于一个大小为 $ n $ 的图 $ G $，我们考虑加入一个点 $ v $。此时我们有 $$ \chi(G-v)+\chi(\overline{G}-v) \leq n $$ 我们现在证明 $ \chi(G) $ 和 $ \chi(\overline{G}) $ 中至多只有一个可能会增加 $ 1 $。设 $ G $ 中 $ v $ 的度数为 $ d(v) $，在 $ \overline{G} $ 中为 $ \overline{d}(v)=n-1-d(v) $。 ...
Problem 1 证明存在常数 $ c > 1 $ 和 $ N > 0 $，使得当 $ n > N $ 时， $ [n] $ 上树的同构类数量至少为 $ c^n $ 。 证 我们需要的同构类的数量则可以看成 $ n $ 个点无标号的树的数量。需要证明这个数量增长的足够快。 首先根据 Cayley 公式，$ n $ 个点的有标号的树的数量为 $ n^{n-2} $。显然所有无标号的树的数量大于 $ \dfrac{n^{n-2}}{n!} $，因为这里直接假设所有点都是对称的，但是实际上一棵有标号的树并不会对应 $ n! $ 颗无标号的树。我们直接取 $ c=2 $，于是就只需要证明存在 $ N>0 $ 满足在 $ n>N $ 时有 $$ \dfrac{n^{n-2}}{n!} > 2^{n} $$ 我们使用斯特林公式，在 $ n $ 足够大时有 $$ n! \approx \sqrt{ 2\pi n }\left( \dfrac{n}{e} \right)^{n} $$ 带入下界，得到 $$ \dfrac{n^{n-2}}{n!} \approx \dfrac{e^{n}}{\sqrt{ 2\pi}\cdot n^{5 / 2}} $$ 所以只需要证明在 $ n>N $ 时有 $$ (\sqrt{ 2\pi })^{1 / n} \cdot n^{5 / 2n} < \dfrac{e}{2} $$ 对于左式，显然有 $$ \lim_{ n \to \infty } [(\sqrt{ 2\pi })^{1 / n} \cdot n^{5 / 2n}] = 1 < \dfrac{e}{2} $$ 根据极限的定义，我们总能找到一个 $ N $ 满足条件。因此得证！ ...
Problem 1 证明 $$ \begin{align*} \sum_{i=0}^{n} (-1)^{i}\binom{ n }{ i } \binom{ n+m-i }{ k-i } = \binom{ m }{ k } \\ \sum_{i=0}^{n} \binom{ k }{ i } D_{n-i} = \sum_{j=0}^{n-k} (-1)^{j}\binom{ n-k }{ j } (n-j)! \end{align*} $$ 证 1 对于第一个式子，我们考虑组合意义。设有 $ A,B $ 两个集合，分别包含 $ n $ 和 $ m $ 个元素，总共 $ n+m $ 个元素。我们希望从集合 $ B $ 中恰好选择 $ k $ 个元素。我们可以通过容斥原理的补集形式求解，定义事件 $ A_{i} $ 为所选的 $ k $ 个元素中至少包含 $ i $ 个来自 $ A $ 的元素，那么我们需要求解的事件集合为 $ U\setminus\bigcup_{i\leq n}A_{i} $，并且 $$ \left| A_{i} \right| = \binom{ n }{ i } \binom{ n+m-i }{ k-i } $$ 因此根据容斥原理，就可以得到 $$ \left| U\setminus \bigcup_{i\leq n}A_{i} \right| = \sum_{i=0}^{n} (-1)^{i}\binom{ n }{ i } \binom{ n+m-i }{ k-i } = \binom{ m }{ k } $$ ...
Principle of Inclusion and Exclusion 对于任意有限集合 $ A_1, A_2, \dots, A_n $，容斥原理如下： $$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{i=1}^{n} \left| A_i \right| - \sum_{1\leq i< j\leq n} \left| A_i \cap A_j \right| + \dots + (-1)^{n} \left| \bigcap_{i=1}^{n} A_i \right| $$ 可更紧凑地表示为 $$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{k=1}^{n} (-1)^{k-1} \sum_{S \subseteq [n], |S|=k} \left| \bigcap_{i \in S} A_i \right| $$ 或 $$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|-1} \left| \bigcap_{i \in S} A_i \right| $$ ...
Problem 1 用生成函数求解递推式 $$ a_{n} = 4a_{n-1} - 5a_{n-2} + 2a_{n-3} $$ 初始值为 $ a_{0}=0,a_{1}=3,a_{2}=7 $。 解： 设数列 $ \{ a_{n} \} $ 的生成函数为 $ F(x) $，那么根据递推式和初值 $ a_{0}=0,a_{1}=3,a_{2}=7 $ 得到 $$ F(x) = 4xF(x) - 5x^{2}F(x) + 2x^{3}F(x) + 3x - 5x^{2} $$ 得到 $$ F(x) = \dfrac{5x^{2}-3x}{2x^{3}-5x^{2}+4x-1} = \dfrac{3x-5x^{2}}{(1-x)^{2}(1-2x)} $$ 我们希望分解成 $$ \dfrac{A}{1-x} + \dfrac{B}{(1-x)^{2}} + \dfrac{C}{1-2x} $$ 待定系数可以解得 $$ F(x) = \dfrac{-3}{1-x} + \dfrac{2}{(1-x)^{2}} + \dfrac{1}{1-2x} $$ 展开得到 $$ F(x) = \sum_{n=0}^{\infty} (-3+2(n+1)+2^{n})x^{n} $$ 因此 $$ a_{n} = -3+2(n+1)+2^{n} = 2^{n} + 2n - 1 $$ ...