猜数字游戏：二叉树模型与通项公式

1. 问题的提出

想象一堂热闹的数学课。老师在黑板上写下“1～100”，心里悄悄想好一个数字，让同学们猜测。老师宣布规则：学生们只能问一个个是非题，例如“是不是大于50？”，看谁能用最少的问题猜出。全班化身侦探，问题此起彼伏：

“是不是大于50？”
“不是？那是不是大于25？”
“还是不是？那是不是大于12？”……

        核心问题：

        直觉表明“每次对半划分”（问中位数）是一个很好的主意。本节将把这个课堂实验，变成一个可以算、能证明的数学问题：在等概率的前提下，如果每次都采用最优的二分策略，平均提问次数（代价） $E(n)$ 到底是多少？如何推导出它的通项公式？

每个问题将候选集合分成两个分叉，因此可以借助二叉树来考虑这个问题。考虑候选集合 $\{1,2,\cdots,8\}$ 的中位数提问策略，根据回答拆分候选集合。将每个数字看作二叉树的一片叶子，数字 $i$ 的叶子深度 $d_i$ 就是它所经历的分叉（提问）次数，在满二叉树中所有 $d_i = 3$。

由于 $E(n)$ 表示平均提问次数，所以 $G(n) = n \cdot E(n)$ 可以看作是所有 $d_i$ 之和。

图 1：平衡二叉树 ($n=8$)

不难发现以下事实：

事实 1：$m$ 次提问最多可以区分 $2^m$ 个数，因此对于给定 $n$，最大的叶深至少有 $m = \lfloor \log_2 n \rfloor$。
事实 2 (裂叶代价)：把一片深度为 $d$ 的叶改成结点并长出两个深度为 $d+1$ 的叶，叶子总数增加 1，叶深和增加 $(2(d+1)-d) = d+2$。

关键推论：基于上述两个事实，可以论证最优二叉树只有 $m$ 和 $m+1$ 两种深度。

如若不然，在二叉树中同时存在一片最浅的叶（深度 $d_{\min}$）与一片最深的叶（深度 $d_{\max} \ge d_{\min} + 2$），我们做两步变换：

经过这两步操作，叶子数不变、叶深和严格下降。反复此操作，直到不再能进行为止；于是所有叶深只能落在 $m$ 与 $m+1$ 两层（否则还能继续下降）。这就得到：最优二叉树只有 $m$ 和 $m+1$ 两种深度。

图 2：不平衡的二叉树向平衡转化

例如图 2 是一个不平衡的二叉树，同时包含了偏浅的叶（深度为 2）和偏深的叶（深度为 4）。将浅叶裂叶，同时合并深叶，便得到了如图 1 所示的严格平衡树。

接下来讨论深度 $m$ 的叶和深度 $m+1$ 的叶的个数。

设深度 $m$ 的叶有 $x$ 个，深度 $m+1$ 的叶有 $y$ 个。显然总叶子数为 $n$：

x + y = n \tag{1}

同时看第 $m$ 层的结点：其总数必定是 $2^m$（为了让树尽可能满）。其中一部分是叶（计 $x$ 个），其余是内部结点；这些内部结点又会长出两片深度为 $m+1$ 的叶，所以：

x + \frac{y}{2} = 2^m \tag{2}

联立式 (1) 和 (2) 解得：

x = 2^{m+1} - n \tag{3} $$ $$ y = 2n - 2^{m+1} \tag{4}

叶深总和 $G(n)$ 可以表示为：

G(n) = m \cdot x + (m+1) \cdot y = m(x+y) + y = mn + 2n - 2^{m+1} \tag{5}

于是平均提问次数 $E(n) = \frac{G(n)}{n}$ 为：

$$ E(n) = m + 2 - \frac{2^{m+1}}{n} = \lfloor \log_2 n \rfloor + 2 - \frac{2^{\lfloor \log_2 n \rfloor + 1}}{n} \tag{7} $$