CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 某个最大反链问题 ======

给定一个非负整数数列 $\{t_{i}\}$，定义偏序集 $S=\prod_{i=1}^{n}\{x|0\le x\le t_{i},x\in\mathbb{Z}\}$，其中 $\vec{x}\preceq\vec{y}$ 当且仅当 $\forall 1\le i\le n,x_{i}\le y_{i}$。那么 $S$ 的最大反链的大小等于关于 $x_{i}$ 的不定方程 $\displaystyle{\sum_{i=1}^{n}x_{i}=\lfloor\frac{\sum_{i=1}^{n}t_{i}}{2}\rfloor}$ 满足 $\forall 1\le i\le n, 0\le x_{i}\le t_{i}$ 的整数解的个数。

**证明**：将该问题用整除来描述：设有整数 $n$，考虑其所有约数组成的集合 $S$，定义 $x\preceq y$ 当且仅当 $x\mid y$。定义 $\deg x$ 为其（可重）质因子数。设 $\deg n=m$。定义 $C=\{x|\deg x=\lfloor\frac{m}{2}\rfloor\}$。我们证明，$S$ 的最大反链大小为 $|C|$，其中 $C$ 显然是一个满足要求的解。

定义对称链为一个序列 $d_{1},d_{2},\cdots,d_{h}$，其中 $\deg d_{1}+\deg d_{h}=m$，$\forall 1\le i<h,\frac{d_{i+1}}{d_{i}}$ 为质数。下面证明一个引理：$S$ 可被划分为若干条对称链。

对 $n$ 的质因子数量进行归纳。$n=1$ 时结论显然成立。考虑 $n'=np^{k}$。对于 $S$ 的每条链与 $p^{0},p^{1},\cdots,p^{k}$ 做笛卡尔积，考虑构造出若干条新对称链：

$$
\begin{matrix}
d_{1}&d_{2}&\cdots&d_{h}\\
d_{1}p&d_{2}p&\cdots&d_{h}p\\
\vdots&\vdots&\ddots&\vdots\\
d_{1}p^{k}&d_{2}p^{k}&\cdots&d_{h}p^{k}
\end{matrix}
$$

在上面的矩形中，每次取第一列和最后一行拼接成一条新链，即 $d_{1},d_{1}p,\cdots,d_{1}p^{k},d_{2}p^{k},\cdots,d_{h}p^{k}$，显然这是一条对称链。引理证毕。

在每一条对称链中，至多含有一个 $C$ 中的元素，由于 $\deg$ 对称且连续，至少含有一个 $C$ 中的元素。因而对称链的数量恰为 $|C|$。根据 Dilworth 定理，原命题成立。
CVBB ACM Team

用户工具

站点工具

页面工具
