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 $ 套。
证
我们转化问题为 $ 20 $ 个数 $ a_{1},a_{2},\dots,a_{20} $ 满足 $ \sum a_{i}=30 $，需要证明存在一段区间 $ [i,j] $ 满足 $$ \sum_{i\leq k\leq j} a_{i} = 9 $$ 我们考虑 $ \{ a_{n} \} $ 的前缀和 $ \{ S_{n} \} $，定义为 $ S_{n}=\sum_{i=1}^{n}a_{i} $，并且我们定义 $ S_{0}=0 $。根据 $ \sum a_{i}=30 $，我们同时也有 $ S_{20}=30 $。这样我们就得到了一个递增的序列 $ T_{1}=\{ 0,S_{1},S_{2},\dots,S_{19},30 \} $。我们需要证明其中存在 $ i,j $ 满足 $ S_{j}-S_{i}=9 $，也就是 $ S_{j}=S_{i}+9 $。
我们考虑集合 $ T_{2}=\{ 9,S_{1}+9,S_{2}+9,\dots,S_{19}+9, 39 \} $。我们只需要证明 $ T_{1}\cap T_{2}\neq \emptyset $。由于 $ T_{1}\cup T_{2} $ 中只会有 $ 0\sim 39 $ 最多 $ 40 $ 个元素，但是 $ \left| T_{1} \right|=\left| T_{2} \right|=21 $，合计 $ 42 $ 个元素。所以根据鸽巢原理，这些元素中肯定有两个相同，并且由于 $ T_{1} $ 是一个递增序列，其中元素不可能相同，所以一定是 $ T_{1},T_{2} $ 中存在元素相同。
所以必然存在 $ S_{j}=S_{i}+9 $，也就是必然存在一段和为 $ 9 $ 的区间。
Problem 3
用三种颜色为 $ K_{17} $ 上的边着色。证明：无论如何着色，必定存在一个单色三角形。
证
我们任取一个点，从这个点会连出 $ 16 $ 条边，根据鸽巢原理，必然有 $ 6 $ 条边的颜色相同，设为蓝色。我们现在考虑这 $ 6 $ 条边连到的这 $ 6 $ 个点。假如这些点之间存在蓝色的边，那么就会和连到这些点的蓝色边构成一个全为蓝色的单色三角形。
否则如果这 $ 6 $ 个点之间的所有边的颜色都为黄色和红色。同理，我们继续考虑任取一个点，这个点会连出 $ 5 $ 条边，根据鸽巢原理，必然存在 $ 3 $ 条边颜色相同，设为红色。我们接着考虑这 $ 3 $ 条红色边连到的 $ 3 $ 个点，如果之间存在红色边，那么就会和连到这些点的红色边构成一个红色三角形；如果不存在红色边，那么这 $ 3 $ 个点本身就会构成一个黄色三角形。
综上，必然会存在一个单色三角形。
Problem 4
(1)
从 $ [2n] $ 中选出 $ n+1 $ 个数。证明其中存在三个数 $ x,y,z $ 满足 $ x+y=z $。
证
我们设这 $ n+1 $ 个数的集合为 $ S_{1} $。我们设 $ S_{1} $ 中最小的元素为 $ m $，令 $$ S_{2} = \{ s-m\mid s \in S_{1},s\neq m \} $$ 表示剩下的元素与 $ s_{1} $ 的差，一共有 $ n $ 个元素。
注意到 $ S_{1},S_{2} $ 中元素的范围都在 $ 1\sim 2n $ 之间，最多只可能有 $ 2n $ 个元素，但是 $ \left| S_{1} \right|+\left| S_{2} \right|=2n+1 $，并且 $ S_{1},S_{2} $ 的元素都互不相同，那么根据鸽巢原理，说明 $ S_{1} $ 和 $ S_{2} $ 中肯定有重合的元素。因此存在 $ p \in S_{1},q\in S_{2} $ 满足 $ p=q-m $，从而取 $ x=m,y=p,z=q $，就满足了 $$ x+y=z $$
(2)
证明只取 $ n $ 个数时结论不成立。
证
我们直接取 $ 1,3,5,\dots,2n-1 $。根据奇偶性，这样的三元组显然不存在。