Math

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-着色方案，与题设矛盾。 因此每个顶点至少属于两条超边。证毕。 ...

Exercise 1 根据对偶变换的定义 $$ (T'(L))(v) = L(T(v)) $$ 带入 $ T(v)=v $，就有 $$ (T'(L))(v) = L(v) $$ 由于这对所有 $ v \in V $ 均成立，从而 $ T'(L) $ 和 $ L $ 是一个函数，因为输入输出完全相同，因此 $ T'(L)=L $，是恒等变换。 Exercise 2 先证充分性，如果 $ T=\mathbf{0} $，那么对于任意 $ v \in V $，都有 $ T(v)=\vec{0} $。根据定义 $$ (T'(L))(v) = L(T(v)) = 0 $$ 说明 $ T'(L) $ 是零泛函，从而 $ T'=\mathbf{0} $。 如果 $ T'=\mathbf{0} $，那么对于任意 $ L\in W' $，$ T'(L) $ 是 $ V $ 上的零泛函。带入定义就有 $$ L(T(v)) =(T'(L))(v) = 0 $$ 由于对所有的线性泛函均成立，那么可以证明 $ T(v)=\vec{0} $。否则将 $ T(v)=w $ 扩充为 $ W $ 的一组基，定义 $ L $ 只在 $ w $ 上为 $ 1 $，否则为 $ 0 $，这样就构造出了一个不符合的 $ L $，因此矛盾。从而 $ T(v)=\vec{0} $ 对所有 $ v $ 均成立，也就有 $ T=\mathbf{0} $。 ...

Problem 1 (1) 总共有 $ N=\binom{ n }{ 2 } $ 对点。设 $ X_{ij}=\mathbb{I}[(i,j)\in E_{n}] $。那么 $ \mathbf{E}[X_{ij}]=p $。并且 $$ \left| E_{n} \right| = \sum_{1\leq i< j\leq n} X_{i} $$ 由于边与边之间独立，因此 $ X_{i} $ 是独立同分布，并且可积，那么根据强大数定律，就有 $$ \dfrac{\sum X_{i}}{N} = \dfrac{\left| E_{n} \right| }{\binom{ n }{ 2 } } \xrightarrow{a.s.} \mathbf{E}[X_{i}]=p $$ (2) 设 $ \mathcal{C}_n $ 为 $ V_n $ 中所有大小为 $ 3 $ 的子集的集合，也就是所有无序三元组 $ \{i, j, k\} $。集合大小 $ |\mathcal{C}_n| = \binom{n}{3} $。 ...

Exercise 1 根据分块对角矩阵的性质，秩等于对角线上各个子块的秩之和，因此 $$ \text{rank}(AB)+n = \text{rank}\left(\begin{bmatrix} AB & 0 \\ 0 & I \end{bmatrix}\right) $$ 接着由于初等列变换不改变矩阵的秩，将第二列右乘 $ B $ 加到第一列得到 $$ \text{rank}\left(\begin{bmatrix} AB & 0 \\ 0 & I \end{bmatrix}\right) = \text{rank}\left(\begin{bmatrix} AB & 0 \\ B & I \end{bmatrix}\right) $$ 同样由于初等行变换也不改变矩阵的秩，将第二行左乘 $ A $ 再和第一行相减，得到 $$ \text{rank}\left(\begin{bmatrix} AB & 0 \\ B & I \end{bmatrix}\right) = \text{rank}\left(\begin{bmatrix} 0 & -A \\ B & I \end{bmatrix}\right) $$ 交换上下两行，得到 $$ \text{rank}\left(\begin{bmatrix} 0 & -A \\ B & I \end{bmatrix}\right) = \text{rank}\left(\begin{bmatrix} B & I \\ 0 & -A \end{bmatrix}\right) $$ 第二行乘以 $ -1 $ 就得到了 $$ \text{rank}\left(\begin{bmatrix} B & I \\ 0 & -A \end{bmatrix}\right) = \text{rank}\left(\begin{bmatrix} B & -I \\ 0 & A \end{bmatrix}\right) $$ 再根据上三角分块矩阵的性质，就有 $$ \text{rank}\left(\begin{bmatrix} B & -I \\ 0 & A \end{bmatrix}\right) \geq \text{rank}(A) + \text{rank}(B) $$ ...

Exercise 1 (1) 对于任意标量 $ c $ 和向量 $ x,y\in U $，都有 $$ \begin{align*} TS(cx+y) & = T(S(cx+y)) \\ & = T(cS(x)+S(y)) \\ & = cT(S(x)) + T(S(y)) \\ & = cTS(x) + TS(y) \end{align*} $$ 从而证明了这是一个线性变换。 (2) 设 $ U,V,W $ 的基为 $$ \bar{u} = \{ u_{1},\dots,u_{p} \},\bar{v}=\{ v_{1},\dots,v_{n} \},\bar{w}=\{ w_{1},\dots,w_{m} \} $$ 根据线性变换矩阵的定义，有 $$ S(u_{i}) = \sum_{k=1}^{n} (A_{S})_{k,i}v_{k},\quad T(v_{i})=\sum_{k=1}^{m} (A_{T})_{k,i}w_{k} $$ 计算 $ TS(u_{i}) $ 并观察系数 $$ \begin{align*} TS(u_{j}) & = T(S(u_{j})) \\ & = T\left( \sum_{k=1}^{n} (A_{S})_{k,j}v_{k} \right) \\ & = \sum_{k=1}^{n} (A_{S})_{k,j}T(v_{k}) \\ & = \sum_{k=1}^{n} (A_{S})_{k,j}\left( \sum_{i=1}^{m} (A_{T})_{i,k}w_{i} \right) \\ & = \sum_{i=1}^{m} \left( \sum_{k=1}^{n} (A_{T})_{i,k}(A_{S})_{k,j} \right)w_{i} \\ & = \sum_{i=1}^{m} (A_{T}A_{S})_{i,j}w_{i} \end{align*} $$ 再结合 $ A_{TS} $ 的定义就证明了 $$ A_{TS}=A_{T}A_{S} $$ ...

Exercise 1 设 $ A $ 的特征多项式为 $ P(\lambda) = \det(A-\lambda I) $。由于特征值 $ \lambda_{1},\lambda_{2},\dots,\lambda_{n} $ 是 $ P(\lambda) $ 的根，因此 $$ P(\lambda) = (-1)^{n}(\lambda-\lambda_{1})(\lambda-\lambda_{2})\dots(\lambda-\lambda_{n}) $$ 我们首先证明 $ \prod_{i=1}^{n}\lambda_{i}=\det(A) $。首先直接带入 $$ P(0)=\det(A-0\cdot I)=\det A $$ 又有 $$ P(0) = (-1)^{n}(0-\lambda_{1})(0-\lambda_{2})\dots(0-\lambda_{n})=\prod_{i=1}^{n} \lambda_{i} $$ 这样就得到了 $ \prod_{i=1}^{n}\lambda_{i}=\det(A) $。 接着证明 $ \sum_{i=1}^{n}\lambda_{i}=\mathrm{trace}(A) $。展开 $ P(\lambda) $ 考察 $ \lambda^{n-1} $ 的系数，为 $$ (-1)^{n}\cdot \sum_{i=1}^{n} (-\lambda_{i}) = (-1)^{n+1}\sum_{i=1}^{n} \lambda_{i} $$ 同时对于矩阵 $ M=A-\lambda I $，利用行列式定义，有 $$ \det(A-\lambda I)=\sum_{\sigma \in S_{n}}\text{sgn}(n)\prod_{i=1}^{n} (A-\lambda I)_{i,\sigma(i)} $$ 其中 $ S_{n} $ 表示 $ [n] $ 中所有置换的集合。 ...

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 (1) 根据泊松分布的定义，我们有 $$ \mathbb{P}[X=\lambda+k] = \dfrac{e^{ -\lambda }\lambda^{\lambda+k}}{(\lambda+k)!},\quad \mathbb{P}[X=\lambda-k-1] = \dfrac{e^{ -\lambda }\lambda^{\lambda-k-1}}{(\lambda-k-1)!} $$ 我们计算两者的比值，有 $$ \dfrac{\mathbb{P}[X=\lambda+k]}{\mathbb{P}[X=\lambda-k-1]} = \dfrac{\lambda^{2k+1}\cdot(\lambda-k-1)!}{(\lambda+k)!} = \dfrac{\lambda^{2k+1}}{(\lambda+k)(\lambda+k-1)\dots(\lambda-k)} $$ 将分母的乘积左右两两配对，得到 $$ (\lambda+k)\dots(\lambda-k) = \lambda \cdot \prod_{i=1}^{k} (\lambda^{2}-k^{2}) > \lambda \cdot \prod_{i=1}^{k} \lambda^{2} = \lambda^{2k+1} $$ 从而就有 $$ \dfrac{\mathbb{P}[X=\lambda+1]}{\mathbb{P}[X=\lambda-k-1]} \geq 1 \implies \mathbb{P}[X=\lambda+1]\geq \mathbb{P}[X=\lambda-k-1] $$ 接着证明 $ \mathbb{P}[X\geq\lambda]\geq \frac{1}{2} $，将事件展开并拆分可以得到 $$ \begin{align*} \mathbb{P}[X\geq \lambda] & =\sum_{k=0}^{\infty} \mathbb{P}[X=\lambda+k] \\ & = \sum_{k=0}^{\lambda-1} \mathbb{P}[X=\lambda+k] + \mathbb{P}[X\geq 2\lambda] \\ & \geq \sum_{k=0}^{\lambda-1} \mathbb{P}[X=\lambda+k] \end{align*} $$ 我们再考虑 $ \mathbb{P}[X< \lambda] $，也就是 $$ \begin{align*} \mathbb{P}[X< \lambda] & = \sum_{k=0}^{\lambda-1} \mathbb{P}[X=\lambda-k-1] \\ & \leq \sum_{k=0}^{\lambda-1} \mathbb{P}[X=\lambda+k] \end{align*} $$ 又因为 $ \mathbb{P}[X\geq\lambda]+\mathbb{P}[X< \lambda]=1 $，这样就得到了 $$ 1-\mathbb{P}[X\geq \lambda] \leq \mathbb{P}[X\geq \lambda] \implies \mathbb{P}[X\geq \lambda] = \dfrac{1}{2} $$ (2) ...

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 (1) 根据题设条件，我们知道最多抽取 $ m $ 个黑球，最少抽取 $ 0 $ 个黑球。设随机变量 $ X $ 表示抽到黑球的个数，根据组合意义，我们得到 $ X $ 的概率质量函数为 $$ \mathbb{P}(X=x) = \dfrac{\binom{ m }{ x } \binom{ n-m }{ k-x } }{\binom{ n }{ k } },\quad x = 0,1,\dots,m $$ (2) 矩生成函数定义为 $ M_{X}(\theta) = \mathbb{E}[e^{ \theta X }] $。我们带入得到 $$ \begin{align*} M_{X}(\theta) & = \sum_{x}e^{ \theta x }\mathbb{P}(X=x) \\ & = \sum_{x=0}^{m} e^{ \theta x } \dfrac{\binom{ m }{ x } \binom{ n-m }{ k-x } }{\binom{ n }{ k } } \\ & = \dfrac{1}{\binom{ n }{ k } }\sum_{x=0}^{m} e^{ \theta x }\binom{ m }{ x } \binom{ n-m }{ k-x } \end{align*} $$ (3) ...