题解：P17227 [Math×Girl²] まよいづき
Galois_Field_1048576
·
·
题解
声明: 写作过程中多次使用 AI 检验并修改病句、斟酌用词与行文,
论证的展开亦有 AI 参与;
思路均出自魔女の理团队的各出题人、验题人及我的个人理解.
约定. 根据个人习惯, 所有数组下标从 0 开始.
这可能影响你对奇数位置等术语的理解.
总结. 把每轮分组表示为完全二叉树. 目标戒指到根的路径外有 n 棵兄弟子树,
每棵都须含一枚较轻戒指, 故编号至多为 2^n-n. 编号取满后,
各子树的重量满足一个递推下界; 把互异正整数分配到这些子树即可得到 m_1
的下界, 构造逐层取等.
题目描述. 有 2^n 枚戒指, 第 i 枚的重量为正整数 m_i, 满足
每轮把当前候选戒指等分为两组, 比较两组重量和, 只保留重量和较大的一组;
保证任一轮两组重量和不相等. 重复 $n$ 轮后恰剩一枚戒指.
可以自行指定全部重量与每轮分组. 求最终保留戒指的最大编号,
并构造达到该编号的重量与分组方案; 在编号最优的构造中, $m_1
越小得分越高.
本节证明如下结论: 最终编号最大为 2^n-n; 且在这个前提下, m_1
的最小值为
\begin{cases}
2,&n=1,\\
5,&n=2,\\
15,&n=3,\\
48,&n=4,\\
\dfrac{9\cdot4^{n-2}+13\cdot2^{n-2}}4+1-n,&n\ge5.
\end{cases}
把筛选过程表示为一棵高度为 n 的完全二叉树 \mathcal T: 叶集 \Lambda
恰为 2^n 枚戒指, 每个内部结点代表一次对决,
两个儿子中叶权和较大的一侧继续向上. 可以任意分组,
故任一策略都对应这样的树, 反之亦然. 对任一子树 u, 记其叶集为
设最终留下的戒指为 $t$, 根到 $t$ 的路径为 $p_0p_1\cdots p_n$ ($p_0
为根, p_n=t). 对 1\le k\le n, 令 B_k 为 p_{k-1}
的另一个儿子所对应的子树. 则这些 B_k 与 t 一起分划叶集:
|\Lambda(B_k)|=2^{n-k},\qquad \Lambda=\{t\}\sqcup\bigsqcup_{k=1}^{n}\Lambda(B_k).
第 k 轮的对决恰发生在结点 p_{k-1}: 比较 B_k 与 p_k 的叶权和. 记
$$w(B_k)<\phi_k\qquad(k=1,\ldots,n).$$
其中 $\phi_n=w(t)$, 且 $\phi_{k-1}=\phi_k+w(B_k)$.
**定理 D.1 (编号上界).** 最终留下的戒指编号至多为 $2^n-n$.
**证明.** 比较规则在整体平移下不变, 故可设 $w(t)=0$. 由 $w(B_k)<\phi_k$ 与
$\phi_{k-1}=\phi_k+w(B_k)$, 有 $\phi_{k-1}<2\phi_k$. 从 $\phi_n=0
反向归纳得 \phi_k<0 (k<n). 因而每个 B_k 的叶权和为负, 至少含一枚比
$p\le N-n$.
$\blacksquare
固定 t=N-n. 编号上界取满时, 恰有 n 枚戒指比 t 轻, 因此每个 B_k
恰含一枚这类戒指, 其余 2^{n-k}-1 枚都比 t 重. 于是 t 之前的
P=N-n-1$ 枚戒指恰为全部较重戒指. 仍设 $w(t)=0$. 设 $B_k
中较重戒指的相对重量之和为 h_k, 唯一较轻戒指的相对重量为 -d_k
(d_k>0), 则 w(B_k)=h_k-d_k; 记 D=\max_k d_k.
引理 D.2 (递推下界). 令 q_k=-\phi_k. 则 q_{k-1}\ge2q_k+1; 因而
**证明.** 由 $w(B_k)<\phi_k=-q_k$ 且权重均为整数, $d_k\ge h_k+q_k+1$. 又
$q_{k-1}=q_k+d_k-h_k\ge2q_k+1$. 由 $q_n=0$ 归纳得 $q_k\ge2^{n-k}-1$,
代回即得结论.
$\blacksquare
注意 2^{n-k}=|\Lambda(B_k)| 正是子树 B_k 的叶数. 第 N
枚戒指的重量为 m_N=m_t-D\ge1, 故 m_t\ge D+1; 这 P
枚较重戒指的相对重量是 P 个互不相同的正整数, 最大者至少为 P, 即
$$m_1\ge P+D+1.$$
于是问题归结为 $D$ 的下界: 每个 $h_k$ 不得超过 $D-2^{n-k}$,
而所有子树要装下 $P$ 个互不相同的正整数.
**定理 D.3 (下界).** $m_1\ge\Phi(n)$.
**证明.** 由 $m_1\ge P+D+1$ 只须证明 $D$ 的下界. 若 $n\le4$, $B_1$ 含 $2^{n-1}-1
枚较重戒指, 其相对重量互不相同, 故 h_1\ge1+\cdots+(2^{n-1}-1);
由递推下界 D\ge d_1\ge h_1+2^{n-1}, 代入该不等式得 m_1\ge2,5,15,48,
恰为 \Phi(1),\ldots,\Phi(4).
若 n\ge5, 令 m=2^{n-2}, 则 N=4m, P=4m-n-1. 两棵子树 B_1,B_2
共含 3m-2 枚较重戒指, 故 h_1+h_2\ge1+\cdots+(3m-2); 而由递推下界
h_1\le D-2m$, $h_2\le D-m$, 解得 $D\ge(9m^2-3m)/4+1=:R$ ($n\ge5
时该数为整数). 于是 m_1\ge P+R+1=\Phi(n).
\blacksquare
引理 D.4 (装箱). 设 n\ge5, m=2^{n-2}, R=(9m-3)m/4+1, P=4m-n-1. 相对重量
恰含 $2^{n-k}-1$ 个数, 其和为 $h_k$, 满足 $h_1=R-2m$, $h_2=R-m-1$, 且
$d_k=h_k+2^{n-k}$ 满足
$$R=d_1>d_2=R-1>d_3>\cdots>d_n=1.$$
**证明.** 取 $3\le k\le n-1$ 时, 令 $L_k$ 为连续区间
$[4m+2-k-2^{n-k+1},\ 4m-k-2^{n-k}]$. 这些区间长度恰为 $2^{n-k}-1$,
首尾相接, 恰好铺满 $\{3m-1,\ldots,P\}$. 令
$L_2=\{7m/4+1,\ldots,9m/4-1\}\cup\{9m/4+1,\ldots,11m/4\}$,
$L_1=\{1,\ldots,3m-2\}\setminus L_2$, $L_n=\varnothing$. 求和即得
$h_1=R-2m$, $h_2=R-m-1$, 故 $d_1=R$, $d_2=R-1$, $d_n=1$.
对 $3\le k\le n-1$, 记 $b=2^{n-k-1}$, $A_k=\min L_k$; 因 $L_{k+1}
紧接在 L_k 之后且 A_k\ge3m-1, 有
d_k-d_{k+1}=b(A_k+1)-\frac{(b-1)(b-2)}2>3mb-\frac{bm}8>0,
故 d 严格递减; 又 R-2-d_3=\dfrac{5m^2}8+3m-3>0, 即
$\blacksquare
定理 D.5 (构造). 对 n\ge5, 取装箱引理中的分配. 设目标戒指 t=N-n, 其重量为 R+1;
P$ 枚较重戒指的重量依次为 $R+2,\ldots,R+P+1$; $B_k
中唯一较轻戒指的重量为 R+1-d_k, 并按 B_n,B_{n-1},\ldots,B_1
的顺序放入. 取对应的完全二叉树. 则第 t 枚戒指最终留下, 且 m_1=R+4m-n
恰为下界.
证明. 有 w(B_k)=h_k-d_k=-2^{n-k}=-|\Lambda(B_k)|. 整体减去 R+1
后目标戒指的相对重量为 0, 且
\phi_k=-\sum_{j=k+1}^{n}2^{n-j}=-(2^{n-k}-1),
故 w(B_k)<\phi_k, 每轮比较的差恰为 1, 全部对决严格成立.
再看重量本身: 较重戒指的重量为 R+2,\ldots,R+P+1, 目标为 R+1, 其余
故全部重量都是互不相同的正整数; 又 $d_1>d_2>\cdots>d_n$,
这些较轻戒指的重量依次递增, 于是整个序列 $m_1>m_2>\cdots>m_{2^n}$ 成立.
特别地
$$m_1=R+1+P=R+4m-n,$$
恰等于下界.
$\blacksquare
对 n\le4, 下列构造中每一轮两组重量和相差 1 (每对 (h_k,d_k)
依次对应 B_1,\ldots,B_n, 目标分别为第 1,2,5,12 枚戒指):
n & \text{重量 }m_1,\ldots,m_{2^n}\ \text{与各 }(h_k,d_k)\\\hline
1 & 2,\ 1;\quad (0,1)\\
2 & 5,\ 4,\ 3,\ 1;\quad (1,3),\ (0,1)\\
3 & 15,\ 14,\ 13,\ 12,\ 11,\ 10,\ 5,\ 1;\quad (6,10),\ (4,6),\ (0,1)\\
4 & 48,\ \ldots,\ 37,\ 36,\ 24,\ 6,\ 1;\quad (28,36),\ (27,31),\ (11,13),\ (0,1)
\end{array}
其中 n=4 的省略号表示 47,46,\ldots,38. 逐一检查即见
综上, 最终编号最大为 $2^n-n$; 在此前提下 $m_1$ 最小为 $\Phi(n)$. 输出时,
先按 $m_1,m_2,\ldots,m_{2^n}$ 输出重量, 再输出每枚戒指的标签: $B_k
中的戒指标签为 k, 目标戒指标签为 0; 第 k 轮把标签为 k
的戒指放入一组, 其余候选者放入另一组即可. 总输出规模为 \mathrm O(2^n).