数学杂题分享 7

周子衡 · 2023-07-09 13:42:51 · 个人记录

题目有 1+2+3+\cdots n\ (=\dfrac{n(n+1)}{2}) 枚一样大小的圆形硬币，堆成一个 n 层的等边三角形，其中第 i\ (1\leq i\leq n) 层恰有 i 枚硬币。在这些硬币中恰有 n 枚是幸运硬币，每层恰有 1 枚。小明在玩一个拿硬币游戏，他总共需要从这些硬币中拿走 n 枚：第 1 枚必须是第 1 层的唯一一枚硬币，第 i\ (2\leq i\leq n) 枚拿走的硬币必须位于第 i 层，必须是位于第 i-1 枚硬币左下角或者右下角的硬币。游戏的目的是尽可能多地拿走幸运硬币。

求最大的整数 k（用 n 表示），使得不论初始时幸运硬币如何分布，小明都能保证拿到至少 k 枚幸运硬币。

（剧透警告）

提示我们有 最长链等于最小反链覆盖 定理。这里给出该定理的一种表述：

定理设 G 是一张有向无环图。对于图上任意两点 u,v，如果存在一条 u,v 之间的（有向）路径，则称 u,v 两点是 可达的。链和反链都是原图顶点的一个子集，其中：

链要求该集合中任意两个不同的点都是可达的；
反链要求该集合中任意两个不同的点都不是可达的。

一个 链覆盖 指的是若干条链，使得图上每个节点都在至少一条链中；反链覆盖 同理。可以注意到任意有向无环图总是存在链覆盖 / 反链覆盖的，这是因为任意只包含一个点的点集既是链也是反链。

我们有如下结论：

（最长反链等于最小链覆盖）图中任意反链包含顶点数的最大值等于任意链覆盖所含链数的最小值。
（最长链等于最小反链覆盖）图中任意链包含顶点数的最大值等于任意反链覆盖所含反链数的最小值。\square

（剧透警告）

上面定理的证明我们放在全文最后，先来看看怎么利用这个定理解决此题。简洁起见，以下我们称第 i 层的幸运硬币为硬币 i。

考虑以 n 枚幸运硬币为顶点建立一张有向无环图，有从硬币 u 指向硬币 v 的有向边当且仅当 u < v 且拿完硬币 u 后可能拿到硬币 v；换句话说，设硬币 i 是第 i 层左数第 a_i 个，那么有向边 u\to v\ (u < v) 存在当且仅当 a_v\in [a_u,a_u+(v-u)]。我们容易发现：

小明拿走的硬币的最大数量即为这张图的最长链长度。

而根据上面的定理，这也自然等于这张图的最小反链覆盖数目。那么，我们要求的 k 本来是所有可能得到的图的最长链长度的最小值，现在就转化成了 最小反链覆盖数目的最小值。在数学上，最小的最小 的处理手段往往比 最大的最小 要多，因而这一步转化是很有机会的。

我们自然考虑，如果我们把硬币 x_1,...,x_n 放在一个反链中，需要满足什么性质。一番探索之后，我们给出本题的核心观察：

引理 1 设 S 是一个正整数集合，其各元素都在 [1,n] 中。那么，存在一种安排幸运硬币的方法，使得能将层数为 S 中元素的各幸运硬币放入一个反链中，当且仅当：S 的元素个数不超过 S 中最小元素的值。

证明我们分两方面来证明。以下设 m 是 S 中的最小元素。

（1）若能将 S 中硬币放入一个反链中，我们考虑这样的操作：对于 \dfrac{n(n+1)}{2} 枚硬币中的每一枚，若它能被 S 中某一枚硬币到达，则将其涂成黑色。注意到：一枚硬币是黑的，当且仅当以下两个条件有一个成立：

它是 S 中的硬币；
它的左上 / 右上的硬币中有黑色的。

这相当于就是说，一枚黑色硬币会将它下方两枚硬币污染成黑色。

假设某一层中有 k\ (k\geq 1) 枚黑色硬币，那么可以发现，即使下一层中没有 S 的元素，它也将至少有 k+1 枚黑色硬币。这是因为，设这一层的黑色硬币分别为从左往右第 b_1,...,b_k 个（这里假定 b_1\sim b_k 是升序排好的），那么下一层的第 b_1,b_2,...,b_k,b_k+1 枚硬币便是 k+1 枚互不相同的、且必定被涂黑的硬币。

于是可以得到结论：从第 m 层开始，每一层的 没有涂黑的硬币数 是单调不增的。（这是因为每一行硬币总数也比上一行多一个。）

进一步地，我们还会发现，若 S 在第 t\ (t > m) 中有元素，那么第 t 层的非黑硬币数严格少于 t-1 层的非黑硬币数。再结合第 m 层有 m-1 枚硬币非黑，我们就得到了结论。

（2）从上面的讨论中已经很容易得到构造了：将每枚幸运硬币放在能放的最左边的位置即可。\square

剩下的部分便是一些常规的分析了。设 S_1,S_2,\cdots,S_{k'} 是原图的一组反链覆盖，m_1,m_2,\cdots,m_{k'} 分别是 S_1\sim S_{k'} 中的最小元素。不妨设 m_i 已按升序排好，我们有：

引理 2 m_i\leq 1+m_1+\cdots +m_{i-1}；特别地，m_1\leq 1（实际上 m_1=1）。

证明显见 m_i 是所有不包含在 S_1,...,S_{i-1} 的幸运硬币的最小层数。由于 S_i 最多包含 m_i 枚硬币，故 S_1\sim S_{i-1} 最多包含 m_1+\cdots +m_{i-1}，证毕。\square

于是可以推得 m_i\leq 2^{i-1}，于是 n\leq m_1+\cdots+m_{k'}=2^{k'}-1，即 k'\geq 1+\lfloor \log_2n\rfloor。另一方面，由上面引理 1 证明中的（2）可得取 m_i=2^{i-1}，S_i=\{2^i,2^i+1,\cdots,\min\{n,2^{i+1}-1\}\} 总是可行的。综上，有

k_{\min}=k'_{\min}=1+\lfloor \log_2n\rfloor

即为所求。\square

对最长链 - 最小反链覆盖定理的证明 方便起见，这里只证明最长链大小等于最小反链覆盖大小，也就是本文实际上用到的定理。首先注意到

结论任意链大小小于任意反链覆盖大小。

证明一条链至多包含一条反链中的一个元素。\square

上面的结论说明了：最长链大小小于等于最小反链覆盖大小。下面我们只需要构造一个大小等于最长链的反链覆盖即可。

注意到一条链事实上指定了一个顺序关系；比如说我们规定若有边 u\to v 就认为 u < v，那么一条链中的任意两个元素都可以比大小。令 h_i 是图中以 i 为最大元素的最长链长度，h 是全图的最长链，那么有：

若 h_i=h_j，那么 i,j 一定不是可比的。（否则若 i < j，则一定有 h_j \geq h_i+1，反之亦然。）

故对每个 t\in [1,h]，全体满足 h_i=t 的节点 i 构成一个反链 S_t。S_1,...,S_h 就是一组反链覆盖，我们即证明了定理。\square

来源本题来自于刚刚结束的 IMO 2023 第二试。