|
|
例 1. 对 $\{1,2, \ldots, n\}$ 的非空子集 $A=\left\{i_{1}<\cdots<i_{t}\right\}$, 定义投影映射 $P_{A}: \mathbf{R}^{n} \rightarrow \mathbf{R}^{t}$ 为
$$
P_{A}\left(x_{1}, \ldots, x_{n}\right)=\left(x_{i_{1}}, \cdots, x_{i_{t}}\right)
$$
设 $K$ 是 $\mathbf{R}^{n}$ 的有限子集, 令 $K_{A}=P_{A}(K)$ 为 $K$ 在投影映射 $P_{A}$ 下的像集.
设 $\mathcal{F}$ 是由 $\{1,2, \ldots, n\}$ 的非空子集构成的族, 满足对每个 $i \in\{1,2, \ldots, n\}$ 都恰好有 $k$ 个 $A \in \mathcal{F}$ 包含 $i$. 证明:
$$
|K|^{k} \leq \prod_{A \in \mathcal{F}}\left|K_{A}\right| .
$$
例 2. 对有限的简单图 $G$, 令 $f(G)$ 为 $G$ 中 $K_{3}$ 的数目, $g(G)$ 为 $G$ 中 $K_{4}$ 的数目. 求最小的常数 $c$, 使得对任何图 $G$ 都有 $g(G)^{3} \leq c \cdot f(G)^{4}$ 成立.
例 3. 设简单图 $G$ 中 $K_{r}$ 的数目为 $C_{x}^{r}=\frac{x(x-1) \cdots(x-r+1)}{r !}$, 其中 $x \geq r$ 是实数, 则 $G$ 中 $K_{r-1}$ 的数目至少为 $C_{x}^{r-1}$.
例 4. 某国共有 10 个城市, 共有 $m$ 个航空公司, 每个航空公司在若干对城市之间运营双向 的航线. 已知对于任何两个航空公司 $A, B$, 它们的航线不全相同, 且对任何城市 $c$, 都存在 城市 $d$, 使得 $c, d$ 之间既有 $A$ 航空公司的航线, 也有 $B$ 航空公司的航线. 求 $m$ 的最大值.
例 5. 给定正整数 $n$, 设整数 $a_{1}, \ldots, a_{n}$ 满足 $a_{1}+\cdots+a_{n}$ 是 $n$ 的倍数. 证明: 存在 $1,2, \ldots, n$ 的两个置换 $\sigma$ 与 $\tau$, 使得对每个 $i=1, \ldots, n$ 都有 $\sigma(i)+\tau(i) \equiv a_{i}(\bmod n)$ 成立.
例 6. 给定正整数 $n>1$, 令 $S$ 为由所有 $n$ 次单位根构成的集合. 设 $P\left(x_{1}, \ldots, x_{n}\right)$ 是 $n$ 个变元的复系数多项式, 满足对 $a_{1}, \ldots, a_{n} \in S$, 等式 $P\left(a_{1}, \ldots, a_{n}\right)=0$ 成立当且仅当 $a_{1}, \ldots, a_{n}$ 两两不同. 求 $P$ 的次数的最小值. |
|
