Project Euler 847
Project Euler 847
题目
Jack’s Bean
Jack has three plates in front of him. The giant has \(N\) beans that he distributes to the three plates. All the beans look the same, but one of them is a magic bean. Jack doesn’t know which one it is, but the giant knows.
Jack can ask the giant questions of the form: “Does this subset of the beans contain the magic bean?” In each question Jack may choose any subset of beans from a single plate, and the giant will respond truthfully.
If the three plates contain \(a\), \(b\) and \(c\) beans respectively, we let \(h(a, b, c)\) be the minimal number of questions Jack needs to ask in order to guarantee he locates the magic bean. For example, \(h(1, 2, 3) = 3\) and \(h(2, 3, 3) = 4\).
Let \(H(N)\) be the sum of \(h(a, b, c)\) over all triples of
non-negative integers \(a\), \(b\), \(c\)
with \(1 \leq a + b + c \leq N\).
You are given: \(H(6) = 203\) and \(H(20) = 7718\).
A repunit, \(R_n\), is a number made up with \(n\) digits all ‘1’. For example, \(R_3 = 111\) and \(H(R_3) = 1634144\).
Find \(H(R_{19})\). Give your answer modulo \(1\,000\,000\,007\).
解决方案
先考虑只有一只盘子、共有 \(n\) 颗豆（\(n\ge 1\)）。每个问题把候选集合分成“在子集里/不在子集里”两部分，因此任何策略都对应一棵二叉判定树，叶子数至少为 \(n\)。故最少问题数满足\(h_1(n)\ge \lceil \log_2 n\rceil.\)而这一下界可达：每次在当前候选集合里取一半大小的子集提问（标准二分定位），即可在 \(\lceil\log_2 n\rceil\) 次内确定唯一豆子。因此\(h_1(n)=\lceil\log_2 n\rceil.\)
对三盘 \((a,b,c)\)，总候选数为\(n=a+b+c.\)无论盘子如何分布，魔法豆都有 \(n\) 种可能位置，故同样有信息论下界\(h(a,b,c)\ge \lceil\log_2 n\rceil.\)记\(k=\lceil\log_2 n\rceil.\)
关键在于：由于每次只能从单盘取子集，确实会出现少数分布使得需要 \(k+1\) 次，但永远不需要 \(k+2\) 次。下面给出一个保证 \(k+1\) 的通用策略：
若某只盘子里至少有 \(2^{k-1}\) 颗豆，则从该盘子取一个大小恰为 \(2^{k-1}\) 的子集提问。
- 若回答“是”，候选缩为单盘 \(2^{k-1}\) 个，余下用 \(h_1(2^{k-1})=k-1\) 次，总计 \(k\) 次。
- 若回答“否”，候选数减少 \(2^{k-1}\) 个，剩余至多 \(n-2^{k-1}\le 2^{k-1}\)，之后同样至多 \(k-1\) 次，总计 \(k\) 次。
若三只盘子都少于 \(2^{k-1}\)，则任取一只盘子（自然会取最多的那只）取其全部豆子提问。若回答“是”则变成单盘问题；若回答“否”，候选落在另外两盘之和。此时最坏情况下可能仍然大于 \(2^{k-1}\)，导致本次提问没有把所需层数从 \(k\) 降到 \(k-1\)，从而整体需要 \(k+1\)。
因此总有\(h(a,b,c)\in\{k,k+1\}.\)令\(z(a,b,c)=h(a,b,c)-\lceil\log_2(a+b+c)\rceil\in\{0,1\}.\)于是\(\displaystyle{H(N)=\sum_{\substack{a,b,c\ge 0\\1\le a+b+c\le N}}\lceil\log_2(a+b+c)\rceil+|Y(N)|,}\)其中
\[ Y(N)=\{(a,b,c)\in\mathbb Z_{\ge0}^3:1\le a+b+c\le N,z(a,b,c)=1\}. \]
接下来分别计算基础项和额外项。
首先计算基础项 \(\displaystyle{W(N)=\sum \lceil\log_2(a+b+c)\rceil},\)对固定总和 \(s=a+b+c\)，非负整数组合数为\(\#\{(a,b,c)\ge0:a+b+c=s\}=\dbinom{s+2}{2}.\)因此\(\displaystyle{W(N)=\sum_{s=1}^{N}\lceil\log_2 s\rceil\binom{s+2}{2}.}\)
设前缀计数\(\displaystyle{F(t)=\sum_{s=1}^{t}\binom{s+2}{2}=\binom{t+3}{3}-1.}\)令 \(L=\lceil\log_2 N\rceil\)，则在区间 \(2^{j-1}<s\le 2^j\) 上有 \(\lceil\log_2 s\rceil=j\)。把区间分块并用 \(F\) 裂项目化简，可得到一个紧凑闭式：
\[ W(N)=L\binom{N+3}{3}-\sum_{j=0}^{L-1}\binom{2^j+3}{3}. \]
接下来计算\(|Y(N)|\)。考虑如下问题：什么时候会出现 \(z(a,b,c)=1\)（即必然需要 \(k+1\) 次）？
取某个时刻的总候选数 \(n\)，满足\(2^K<n\le 2^{K+1},\)此时理论下界为 \(K+1\)。若某盘 \(\ge 2^K\)，则可以一次取 \(2^K\) 个保证把规模降到 \(\le 2^K\)，从而在 \(K+1\) 内完成。
临界困难情形出现在三只盘子的豆子数都小于 \(2^K\) 时。此时任意一次提问，从单盘中最多也只能取到一个小于 \(2^K\) 的子集。若希望不产生额外开销（即仍能在 \(K+1\) 轮内结束），就必须存在某一盘及其子集大小 \(s\)，使两种回答后的候选规模都不超过 \(2^K\)，也就是同时满足 \(s\le 2^K\) 和 \(n-s\le 2^K\)。由于 \(s\) 还受该盘容量限制，当“某两盘之和 \(\le 2^K\)”时，这个条件总能实现（对第三盘提问并选取足够大的子集）。反过来，若任意两盘之和都至少 \(2^K+1\)，那么无论问哪一盘、取多大子集，总会有一个分支保留超过 \(2^K\) 个候选，因此无法在 \(K+1\) 轮内完成，只能需要 \(K+2\) 轮（即相对下界多 \(1\)），这正是 \(z=1\) 的来源。
将三盘参数平移为\((x,y,z)=(2^{K-1}+a,2^{K-1}+b,2^{K-1}+c).\)则条件任意两盘之和 \(\ge 2^K+1\)可直接改写为\(a+b\ge 1, a+c\ge 1, b+c\ge 1.\)
另一方面，因为当前讨论的是第 \(K\) 层（即总数满足 \(x+y+z\le 2^{K+1}\)），所以\(a+b+c= x+y+z-3\cdot 2^{K-1}\le 2^{K-1}.\)
据此定义\(T(t)=\left\{(a,b,c)\in\mathbb Z^3:a+b\ge1,a+c\ge1,b+c\ge1,a+b+c\le t\right\}.\)于是，第 \(K\) 层中所有会触发额外一步的临界分布，正好对应于集合 \(T(t)\) 在不同上界 \(t\) 下的截断。
令 \(t\ge 1\)，考虑壳层 \(a+b+c=t\) 的元素数。作线性变换\((d,e,f)=(a+b,a+c,b+c).\)则条件 \(a+b,a+c,b+c\ge1\) 等价于 \(d,e,f\in\mathbb Z_{\ge1}\)。并且\(d+e+f=2(a+b+c)=2t.\)
反过来由\(a=\dfrac{d+e-f}{2}, b=\dfrac{d+f-e}{2}, c=\dfrac{e+f-d}{2},\) 可知当 \(d+e+f\) 为偶数时这是双射，因此壳层大小就是正整数解\(d+e+f=2t,d,e,f\ge 1\)的个数，即隔板法\(\dbinom{2t-1}{2}.\) 把它改写成更便于求和的形式：\(\dbinom{2t-1}{2}=3\dbinom{t}{2}+\dbinom{t-1}{2}.\)于是
\[ \tau(X)=|T(X)| =\sum_{t=1}^{X}\binom{2t-1}{2} =\sum_{t=1}^{X}\left(3\binom{t}{2}+\binom{t-1}{2}\right) =3\binom{X+1}{3}+\binom{X}{3}. \]
并规定 \(\tau(X)=0\) 当 \(X\le 0\)。
这时，还需要把在某一层 \(K\) 触发额外一步与初始总豆子数 \(\le N\) 联系起来。
设初始总数 \(n_0\) 满足\(2^m<n_0\le 2^{m+1}.\)在理想推进下，会先在层 \(m,m-1,\dots\) 依次尝试消去大小为 \(2^m,2^{m-1},\dots\) 的整块（当对应盘子容量允许时）。若在消去 \(2^m,2^{m-1},\dots,2^{k+1}\) 的这 \(m-k\) 步中，巨人的回答都为“否”，则总候选数共减少\(2^m+2^{m-1}+\cdots+2^{k+1}=2^{m+1}-2^{k+1}.\)随后进入第 \(k\) 层，此时总候选数 \(n\) 同时受到两类上界约束：层内限制：\(n\le 2^{k+1}\)；初始上界：\(n\le N-(2^{m+1}-2^{k+1})\)。
因此\(n\le \min(2^{k+1},N-(2^{m+1}-2^{k+1})).\)代入 \(a+b+c=n-3\cdot 2^{k-1}\)，可得临界集合的截断参数满足\(a+b+c\le \min(2^{k-1},N-2^{m+1}+2^{k-1})=\min(N-2^{m+1},0)+2^{k-1}.\)所以在给定 \((m,k)\) 下，临界分布的数量为
\[\tau(\min(N-2^{m+1},0)+2^{k-1}).\]
最后还要乘上一个系数：在前面 \(m-k\) 次消去整块的过程中，每一步都可能是三只盘子中的任意一只承担那块 \(2^j\)（盘子是带标签的），这产生 \(3^{m-k}\) 种历史选择，且都会把计数同样带到这一层。因此
\[ Z(N)=|Y(N)|=\sum_{m\ge 0}\sum_{1\le k\le m}3^{m-k}\tau\left(\min(N-2^{m+1},0)+2^{k-1}\right). \]
当 \(2^{m+1}\) 已经大到使得截断参数非正时，\(\tau\) 为 \(0\)，故双重求和只需到 \(O(\log N)\) 的范围，总复杂度为 \(O((\log N)^2)\)。
综合以上，最终得到结果\(H(N)=W(N)+Z(N).\)
代码
1 | N = 1111111111111111111 |