又到了快乐概率论的时候了。

原因是昨天打了一个野心家甄姬蒋干，对面是司马懿张合、邓艾夏侯敦、荀攸张辽、郭嘉曹操。盟友孙坚鲁迅直接杀了另外两个盟友(没有曹丕为什么不能挣扎)，被迫1。V4.三只魏狗成功干翻（等等，我好像也是），不幸的是，最后一场激战单挑竟然输给了邓艾夏侯敦，真的很丢人（要不然就能放出来给大家炫耀一下了）。

作者知耻后勇，决心挑灯夜战计算蒋干盗书最优策略。

蒋干的核心技能是盗书，具体文字定义如下：

定义 1 1 1(蒋干盗书文字说明)：

你可以选择另一个角色，选择一种颜色(，)，然后得到这个角色的手牌:

1. 如果这张牌和你选择的颜色一样，你会对它造成一点伤害，这个技能被认为没有启动；

2. 如果这张牌和你选择的颜色不一样，你会给这个角色一张其他颜色的手牌(如果你不需要展示所有的手牌)；

从定义 1 1 1中可以看出，蒋干盗书上限很高，只要能猜对别人手牌的颜色，就能不断发动盗书(即不断触发定义 1 1 1 理论上，欧洲皇帝蒋干可以从一开始就偷走所有的手牌（顺便说一句，造成了巨大的伤害）。然而，大多数时候，蒋干就像咸鱼一样。他只是和别人换了手牌就放弃了牌。

其实这并不难理解，蒋干在没有任何先验信息的情况下发动了盗书成功率仅为 1 / 4 1/4 1/4，期待蒋干通过盗书获得的手牌数为： E r a n d o m ( X ) = ∑ k = 1 ∞ 1 4 k = 1 3 (1) \mathbb{E}_{\rm random}(X)=\sum_{k=1}^{ \infty}\frac{1}{4^k}=\frac13\tag{1} Erandom(X)=k=1∑+∞​4k1​=31​(1) 实战中蒋干想要获取关于手牌的先验信息非常困难，在不考虑其他武将技能的条件下，仅能通过火攻（别人展示一张明牌）与五谷丰登（别人获得一张明牌）收集先验信息，而仅仅一张明牌的先验信息很多时候并不足以改变蒋干咸鱼的本质。

因此蒋干的主场显然是在国战：

1. 魏国将池中有大量可以为蒋干提供手牌先验信息的搭配武将（荀攸、于禁、郭嘉、崔琰毛玠）；
2. 魏国将池中还有大量可以破坏别人手牌结构的搭配武将（张辽、张郃、邓艾、荀彧），同样可以提升盗书成功率；
3. 曹丕的放逐使得蒋干能够对同一个人连续发动两轮盗书，大大提升成功率；
4. 李典看似与蒋干并无相性，事实上这个组合的上限是蒋干所有搭配中最高的；

最最关键的是，国战牌堆中有一张专属锦囊知己知彼能够直接观看他人手牌：

尽管知己知彼无法获得有效的手牌次序，但是在已知手牌的各花色数量的条件下进行盗书，此时成功率显然是非常可观的。

因此，本文将通过理论证明与仿真验证的研究方法，着重探讨在知己知彼提供的明牌条件（即已知手牌中各个花色的数量构成）下及其各个变体的盗书策略。

首先将问题抽象为标准的数学描述：

问题 1 1 1（明牌盗书）：

已知可重集（即可以包含重复元素的集合） U = { x 1 , x 2 , . . . , x n } U=\{x_1,x_2,...,x_n\} U={ x1​,x2​,...,xn​}中包含 n n n个元素，其中 x i ∈ { 1 , 2 , . . . , k } , i = 1 , 2 , . . . , n x_i\in\{1,2,...,k\},i=1,2,...,n xi​∈{ 1,2,...,k},i=1,2,...,n。从 U U U中不放回地依次采样一个元素，并猜测本次采样得到的元素对应的数值，直到猜测错误为止。

令上述过程中猜测正确的次数为 X X X，则使得随机变量 X X X的数学期望最大的猜测策略是什么？此时随机变量 X X X的数学期望 E b a s e ( X ) \mathbb{E}_{\rm base}(X) Ebase​(X)是多少？

在蒋干盗书的环境下，问题 1 1 1 中的 U U U即为手牌集合， k ≤ 4 k\le 4 k≤4为花色数量（元素种类），此处不妨设 U U U中包含每种花色的手牌至少有一张。

注意到，我们关注的是最大化猜测正确次数 X X X的数学期望，举一个简单的例子，假定 U = { 1 , 1 , 2 , 2 , 3 } U=\{1,1,2,2,3\} U={ 1,1,2,2,3}，下面是两种不同猜测策略对应 X X X的分布列：

• 优先猜测 U U U中包含数量最多的元素，即 1 → 2 → 1 → 2 → 3 1\rightarrow2\rightarrow1\rightarrow2\rightarrow3 1→2→1→2→3：

  X X X	0 0 0	1 1 1	2 2 2	3 3 3	4 4 4	5 5 5
  概率	3 5 \frac35 53​	2 5 ⋅ 2 4 = 1 5 \frac25\cdot\frac24=\frac15 52​⋅42​=51​	2 5 ⋅ 2 4 ⋅ 2 3 = 2 15 \frac25\cdot\frac24\cdot\frac23=\frac2{15} 52​⋅42​⋅32​=152​	2 5 ⋅ 2 4 ⋅ 1 3 ⋅ 1 2 = 1 30 \frac25\cdot\frac24\cdot\frac13\cdot\frac12=\frac1{30} 52​⋅42​⋅31​⋅21​=301​	0 0 0	2 5 ⋅ 2 4 ⋅ 1 3 ⋅ 1 2 = 1 30 \frac25\cdot\frac24\cdot\frac13\cdot\frac12=\frac1{30} 52​⋅42​⋅31​⋅21​=301​

  可以计算 X X X的数学期望： μ 1 = E ( X ) = 0 ⋅ 3 5 + 1 ⋅ 1 5 + 2 ⋅ 2 15 + 3 ⋅ 1 30 + 4 ⋅ 0 + 5 ⋅ 1 30 = 11 15 (2) \mu_1=\mathbb E(X)=0\cdot\frac35+1\cdot\frac15+2\cdot\frac2{15}+3\cdot\frac1{30}+4\cdot 0+5\cdot\frac1{30}=\frac{11}{15}\tag{2} μ1​=E(X)=0⋅53​+1⋅51​+2⋅152​+3⋅301​+4⋅0+5⋅301​=1511​(2)

• 随机猜测 U U U中的元素，比如 3 → 1 → 2 → 1 → 2 3\rightarrow1\rightarrow2\rightarrow1\rightarrow2 3→1→2→1→2：

  X X X	0 0 0	1 1 1	2 2 2	3 3 3	4 4 4	5 5 5
  概率	4 5 \frac45 54​	1 5 ⋅ 2 4 = 1 10 \frac15\cdot\frac24=\frac1{10} 51​⋅42​=101​	1 5 ⋅ 2 4 ⋅ 1 3 = 1 30 \frac15\cdot\frac24\cdot\frac13=\frac1{30} 51​⋅42​⋅31​=301​	1 5 ⋅ 2 4 ⋅ 2 3 ⋅ 1 2 = 1 30 \frac15\cdot\frac24\cdot\frac23\cdot\frac12=\frac1{30} 51​⋅42​⋅32​⋅21​=301​	0 0 0	2 5 ⋅ 2 4 ⋅ 1 3 ⋅ 1 2 = 1 30 \frac25\cdot\frac24\cdot\frac13\cdot\frac12=\frac1{30} 52​⋅42​⋅31​⋅21​=301​

  同理计算 X X X的数学期望： μ 2 = E ( X ) = 0 ⋅ 4 5 + 1 ⋅ 1 10 + 2 ⋅ 1 30 + 3 ⋅ 1 30 + 4 ⋅ 0 + 5 ⋅ 1 30 = 13 30 (3) \mu_2=\mathbb E(X)=0\cdot\frac45+1\cdot\frac1{10}+2\cdot\frac1{30}+3\cdot\frac1{30}+4\cdot 0+5\cdot\frac1{30}=\frac{13}{30}\tag{3} μ2​=E(X)=0⋅54​+1⋅101​+2⋅301​+3⋅301​+4⋅0+5⋅301​=3013​(3)

通过上面的计算，肯定有朋友已经发现，最优策略当然是每次猜测集合 U U U中包含数量最多的那种元素（即盗书选择手牌中花色最多的花色），然而该策略的最优性是显然的吗？至少笔者认为这并不那么显然，尽管这是正确的。

该最优策略将贯穿本文的全部内容，笔者需要严谨地对其进行证明。

为了证明每次猜测集合 U U U中包含数量最多的那种元素是明牌条件下的最优策略，我们希望能够获得 E b a s e ( X ) \mathbb{E}_{\rm base}(X) Ebase​(X)的具体表达式。

其实观察 1.1 1.1 1.1节中例子 U = { 1 , 1 , 2 , 2 , 3 } U=\{1,1,2,2,3\} U={ 1,1,2,2,3}的分布列计算过程，可以首先求解一个新的辅助分布列来快速计算分布列中的每个概率值：

定义 1 1 1（辅助分布列）：

已知可重集（即可以包含重复元素的集合） U = { x 1 , x 2 , . . . , x n } U=\{x_1,x_2,...,x_n\} U={ x1​,x2​,...,xn​}中包含 n n n个元素，其中 x i ∈ { 1 , 2 , . . . , k } , i = 1 , 2 , . . . , n x_i\in\{1,2,...,k\},i=1,2,...,n xi​∈{ 1,2,...,k},i=1,2,...,n。从 U U U中不放回地依次采样一个元素，并猜测本次采样得到的元素对应的数值，直到猜测错误为止。

给定一个猜测序列 G G G（即 U U U中所有元素的一个排列，如 1 → 2 → 1 → 2 → 3 1\rightarrow2\rightarrow1\rightarrow2\rightarrow3 1→2→1→2→3表示为 { 1 , 2 , 1 , 2 , 3 } \{1,2,1,2,3\} { 1,2,1,2,3}），则 G G G对应的辅助分布列 [ p 1 , p 2 , . . . , p n ] [p_1,p_2,...,p_n] [p1​,p2​,...,pn​]定义为： p i = { Pr ⁡ ( 猜 对 G 中 第 1 个 元 素 ) ( i = 1 ) Pr ⁡ ( 猜 对 G 中 第 i 个 元 素 ∣ 猜 对 G 中 前 ( i − 1 ) 个 元 素 ) ( i = 2 , . . . , n ) (4) p_i=\left\{\begin{aligned} &\Pr(猜对G中第1个元素)&&(i=1)\\ &\Pr(猜对G中第i个元素|猜对G中前(i-1)个元素)&&(i=2,...,n) \end{aligned}\right.\tag{4} pi​={ ​Pr(猜对G中第1个元素)Pr(猜对G中第i个元素∣猜对G中前(i−1)个元素)​​(i=1)(i=2,...,n)​(4) 或者更标准地，定义事件 T i T_i Ti​表示猜对 G G G中第 i i i个元素，则： p i = { Pr ⁡ ( T 1 ) ( i = 1 ) Pr ⁡ ( T i ∣ T 1 , T 2 , . . . , T i − 1 ) ( i = 1 , 2 , . . . , n ) (5) p_i=\left\{\begin{aligned} &\Pr(T_1)&&(i=1)\\ &\Pr(T_i|T_1,T_2,...,T_{i-1})&&(i=1,2,...,n) \end{aligned}\right.\tag{5} pi​={ ​Pr(T1​)Pr(Ti​∣T1​,T2​,...,Ti−1​)​​(i=1)(i=1,2,...,n)​(5)

具体而言，仍然以 U = { 1 , 1 , 2 , 2 , 3 } U=\{1,1,2,2,3\} U={ 1,1,2,2,3}为例，按照 1 → 2 → 1 → 2 → 3 1\rightarrow2\rightarrow1\rightarrow2\rightarrow3 1→2→1→2→3的顺序猜测，即 G = { 1 , 2 , 1 , 2 , 3 } G=\{1,2,1,2,3\} G={ 1,2,1,2,3}，辅助分布列为：

这里笔者特意没有给分子分母进行约分，为的就是更清晰地看出分子分母的含义：

• p 1 = 2 / 5 p_1=2/5 p1​=2/5：猜测的是 1 1 1，分子表示此时 U U U中还有 2 2 2个 1 1 1，分母表示此时 U U U中还有 5 5 5个元素；
• p 2 = 2 / 4 p_2=2/4 p2​=2/4：猜测的是 2 2 2，分子表示此时 U U U中还有 2 2 2个 2 2 2，分母表示此时 U U U中还有 4 4 4个元素；
• p 3 = 1 / 3 p_3=1/3 p3​=1/3：猜测的是 1 1 1，分子表示此时 U U U中还有 1 1 1个 1 1 1，分母表示此时 U U U中还有 3 3 3个元素；
• p 4 = 1 / 2 p_4=1/2 p4​=1/2：猜测的是 2 2 2，分子表示此时 U U U中还有 1 1 1个 2 2 2，分母表示此时 U U U中还有 2 2 2个元素；
• p 5 = 1 / 1 p_5=1/1 p5​=1/1：猜测的是 3 3 3，分子表示此时 U U U中还有 1 1 1个 3 3 3，分母表示此时 U U U中还有 1 1 1个元素；任何情况下辅助分布列中的最后一个数值都是 1 1 1

那么根据辅助分布列可以快速求得分布列的数值，具体如下面的定理所述：

定理 1 1 1（根据辅助分布列求解分布列）：

在问题 1 1 1 的条件下，已知猜测序列 G G G的辅助分布列为 [ p 1 , p 2 , . . . , p n ] [p_1,p_2,...,p_n] [p1​,p2​,...,pn​]，则猜测序列 G G G的分布列为： X Probability 0 1 − p 1 1 p 1 ( 1 − p 2 ) 2 p 1 p 2 ( 1 − p 3 ) 3 p 1 p 2 p 3 ( 1 − p 4 ) . . . . . . n − 1 p 1 p 2 . . . p n − 1 ( 1 − p n ) n p 1 p 2 . . . . p n − 1 p n (6) \begin{aligned} &X&\text{Probability}\\ &0&1-p_1\\ &1&p_1(1-p_2)\\ &2&p_1p_2(1-p_3)\\ &3&p_1p_2p_3(1-p_4)\\ &...&...\\ &n-1&p_1p_2...p_{n-1}(1-p_{n})\\ &n&p_1p_2....p_{n-1}p_n \end{aligned}\tag{6} ​X0123...n−1n​Probability1−p1​p1​(1−p2​)p1​p2​(1−p3​)p1​p2​p3​(1−p4​)...p1​p2​...pn−1​(1−pn​)p1​p2​....pn−1​pn​​(6) 证明略。

注意到，因为 p n ≡ 1 p_n\equiv1 pn​≡1，因此 X = n − 1 X=n-1 X=n−1的概率总是为零，这与 1.1 1.1 1.1节中的结果相吻合。直观上不可能猜错最后一张手牌（此时必然是一张明牌），因此不可能只少猜对一张牌。

定理 1 1 1 非常简单，因而省略证明，但是它能够提供 E b a s e ( X ) \mathbb{E}_{\rm base}(X) Ebase​(X)关于辅助分布列的简明表达式： E b a s e ( X ) = p 1 + p 1 p 2 + p 1 p 2 p 3 + . . . + p 1 p 2 . . . p n = ∑ i = 1 n ( ∏ k = 1 i p k ) (7) \mathbb{E}_{\rm base}(X)=p_1+p_1p_2+p_1p_2p_3+...+p_1p_2...p_n=\sum_{i=1}^n\left(\prod_{k=1}^i p_k\right)\tag{7} Ebase​(X)=p1​+p1​p2​+p1​p2​p3​+...+p1​p2​...pn​=i=1∑n​(k=1∏i​pk​)(7) 这在下面的证明中将非常重要。

现在我们可以来说明每次猜测集合 U U U中包含数量最多的那种元素是明牌条件下的最优策略。

定理 2 2 2（明牌条件下的盗书最优策略）：

问题 1 1 1 的最优策略是每次猜测集合 U U U中包含数量最多的那种元素（如果有多种元素数量同为最多，则任意挑选其中一种即可）。

证明：反证法。

定义 a i a_i ai​（ i = 1 , 2 , . . . , k i=1,2,...,k i=1,2,...,k）表示 U U U中取值为 i i i的元素数量（即每种花色对应的手牌数量）。

不妨设 a 1 > a 2 ≥ a 3 ≥ . . . ≥ a n a_1\gt a_2\ge a_3\ge...\ge a_n a1​>a2​≥a3​≥...≥an​，为了方便说明，这里假定包含数量最多的那种元素是唯一的（即 a 1 a_1 a1​严格大于 a 2 a_2 a2​），若有多种元素数量同为最多，证明过程是相仿的。

对于某个猜测序列 G = { x g 1 , x g 2 , . . . , x g n } G=\{x_{g_1},x_{g_2},...,x_{g_n}\} G={ xg1​​,xg2​​,...,xgn​​}，假定其中第一次出现 1 1 1的位置是在 x g m x_{g_m} xgm​​，即有： x g 1 ≠ 1 , x g 2 ≠ 1 , . . . , x g m − 1 ≠ 1 , x g m = 1 (8) x_{g_1}\neq1,\quad x_{g_2}\neq 1,\quad ...,\quad x_{g_{m-1}}\neq1,\quad x_{g_{m}}=1\tag{8} xg1​​​=1,xg2​​​=1,...,xgm−1​​​=1,xgm​​=1(8) 此时新构造的猜测序列 G ′ = { 1 , x g 1 , x g 2 , . . . , x g m − 1 , x g m + 1 , . . . , x g n } G'=\{1,x_{g_1},x_{g_2},...,x_{g_{m-1}},x_{g_{m+1}},...,x_{g_{n}}\} G′={ 1,xg1​​,xg2​​,...,xgm−1​​,xgm+1​​,...,xgn​​}（即优先猜测包含数量最多的那种元素），利用式 ( 7 ) (7) (7)，我们试图证明，根据 G ′ G' G′计算得到的 E b a s e ′ ( X ) \mathbb{E}'_{\rm base}(X) Ebase′​(X)总是不小于根据 G G G计算得到的 E b a s e ( X ) \mathbb{E}_{\rm base}(X) Ebase​(X)：

• 设 G G G与 G ′ G' G′的辅助分布列分别为 [ p 1 , p 2 , . . . , p n ] [p_1,p_2,...,p_n] [p1​,p2​,...,pn​]与 [ p 1 ′ , p 2 ′ , . . . , p n ′ ] [p_1',p_2',...,p_n'] [p1′​,p2′​,...,pn′​]，定义 f G ( U ) f_G(U) fG​(U)与 f G ′ ( U ) f_{G'}(U) fG′​(U)分别表示在猜测序列 G G G与 G ′ G' G′下的猜对次数的数学期望。

• 显然，从第 m + 1 m+1 m+1次猜测往后， G G G与 G ′ G' G′是完全都是相同的，即有： p i = p i ′ ∀ i = m + 1 , m + 2 , . . . , n (9) p_i=p_i'\quad \forall i=m+1,m+2,...,n\tag{9} pi​=pi′​∀i=m+1,m+2,...,n(9)

• 对于每个 i ≤ m i\le m i≤m，根据 1.2 1.2 1.2节中描述的辅助分布列的计算规律，可以得到形式： p 1 = y 1 n p 1 ′ = a 1 n p 2 = y 2 n − 1 p 2 ′ = y 1 n − 1 p 3 = y 3 n − 2 p 3 ′ = y 2 n − 2 . . . . . . p m − 1 = y m − 1 n − m + 2 p m − 1 ′ = y m − 2 n − m + 2 p m = a 1 n − m + 1 p m ′ = y m − 1 n − m + 1 (10) \begin{aligned} &p_1=\frac{y_1}{n}&&p_1'=\frac{a_1}{n}\\ &p_2=\frac{y_2}{n-1}&&p_2'=\frac{y_1}{n-1}\\ &p_3=\frac{y_3}{n-2}&&p_3'=\frac{y_2}{n-2}\\ &...&&...\\ &p_{m-1}=\frac{y_{m-1}}{n-m+2}&&p_{m-1}'=\frac{y_{m-2}}{n-m+2}\\ &p_{m}=\frac{a_1}{n-m+1}&&p_m'=\frac{y_{m-1}}{n-m+1}\\ \end{aligned}\tag{10} ​p1​=ny1​​p2​=n−1y2​​p3​=n−2y3​​...pm−1​=n−m+2ym−1​​pm​=n−m+1a1​​​​p1′​=na1​​p2′​=n−1y1​​p3′​=n−2y2​​...pm−1′​=n−m+2ym−2​​pm′​=n−m+1ym−1​​​(10) 其中 y 1 , . . . , y m − 1 y_1,...,y_{m-1} y1​,...,ym−1​表示对应当前猜测时， U U U中还剩下的 x g 1 , . . . , x g m − 1 x_{g_{1}},...,x_{g_{m-1}} xg1​​,...,xgm−1​​的数量，显然有 y i < a 1 y_i<a_1 yi​<a1​（ i = 1 , 2 , . . . , m − 1 i=1,2,...,m-1 i=1,2,...,m−1）成立。

• 根据式 ( 9 ) (9) (9)与式 ( 10 ) (10) (10)的规律，代入到式 ( 7 ) (7) (7)中可得 G G G与 G ′ G' G′对应的数学期望值： E b a s e ( X ) = f G ( U ) = p 1 + p 1 p 2 + . . . + p 1 p 2 . . . p m ( 1 + p m + 1 + p m + 1 p m + 2 + . . . + p m + 1 p m + 2 . . . p n ) E b a s e ′ ( X ) = f G ′ ( U ) = p 1 ′ + p 1 ′ p 2 ′ + . . . + p 1 ′ p 2 ′ . . . p m ′ ( 1 + p m + 1 ′ + p m + 1 ′ p m + 2 ′ + . . . + p m + 1 ′ p m + 2 ′ . . . p n ′ ) (11) \mathbb{E}_{\rm base}(X)=f_G(U)=p_1+p_1p_2+...+p_1p_2...p_m(1+p_{m+1}+p_{m+1}p_{m+2}+...+p_{m+1}p_{m+2}...p_{n})\\ \mathbb{E}_{\rm base}'(X)=f_{G'}(U)=p_1'+p_1'p_2'+...+p_1'p_2'...p_m'(1+p_{m+1}'+p_{m+1}'p_{m+2}'+...+p_{m+1}'p_{m+2}'...p_{n}')\tag{11}\\ Ebase​(X)=fG​(U)=p1​+p1​p2​+...+p1​p2​...pm​(1+pm+1​+pm+1​pm+2​+...+pm+1​pm+2​...pn​)Ebase′​(X)=fG′​(U)=p1′​+p1′​p2′​+...+p1′​p2′​...pm′​(1+pm+1′​+pm+1′​pm+2′​+...+pm+1′​pm+2′​...pn′​)(11) 显然式 ( 11 ) (11) (11)中两行各自的最后一项括号中的部分完全相等。

  因为 a 1 a_1 a1​比每一个 y i y_i yi​（ i = 1 , 2 , . . . , m − 1 i=1,2,...,m-1 i=1,2,...,m−1）都要严格地大，容易发现有： a 1 n > y 1 n ⟹ p 1 ′ > p 1 a 1 y 1 n ( n − 1 ) > y 1 y 2 n ( n − 1 ) ⟹ p 1 ′ p 2 ′ > p 1 p 2 a 1 y 1 y 2 n ( n − 1 ) ( n − 2 ) > y 1 y 2 y 3 n ( n − 1 ) ( n − 2 ) ⟹ p 1 ′ p 2 ′ p 3 ′ > p 1 p 2 p 3 . . . . . . a 1 y 1 y 2 . . . y m − 2 n ( n − 1 ) . . . ( n − m + 2 ) > y 1 y 2 y 3 . . . y m − 1 n ( n − 1 ) . . . ( n − m + 2 ) ⟹ p 1 ′ p 2 ′ . . . p m − 1 ′ > p 1 p 2 . . . p m − 1 a 1 y 1 y 2 . . . y m − 2 y m − 1 n ( n − 1 ) . . . ( n − m + 1 ) = y 1 y 2 y 3 . . . y m − 1 a 1 n ( n − 1 ) . . . ( n − m + 1 ) ⟹ p 1 ′ p 2 ′ . . . p m − 1 ′ p m ′ = p 1 p 2 . . . p m − 1 p m (12) \begin{aligned} &\frac{a_1}{n}>\frac{y_1}{n}&&\Longrightarrow p_1'>p_1\\ &\frac{a_1y_1}{n(n-1)}>\frac{y_1y_2}{n(n-1)}&&\Longrightarrow p_1'p_2'>p_1p_2\\ &\frac{a_1y_1y_2}{n(n-1)(n-2)}>\frac{y_1y_2y_3}{n(n-1)(n-2)}&&\Longrightarrow p_1'p_2'p_3'>p_1p_2p_3\\ ...&&...\\ &\frac{a_1y_1y_2...y_{m-2}}{n(n-1)...(n-m+2)}>\frac{y_1y_2y_3...y_{m-1}}{n(n-1)...(n-m+2)}&&\Longrightarrow p_1'p_2'...p_{m-1}'>p_1p_2...p_{m-1}\\ &\frac{a_1y_1y_2...y_{m-2}y_{m-1}}{n(n-1)...(n-m+1)}=\frac{y_1y_2y_3...y_{m-1}a_1}{n(n-1)...(n-m+1)}&&\Longrightarrow p_1'p_2'...p_{m-1}'p_{m}'=p_1p_2...p_{m-1}p_m\\ \end{aligned}\tag{12} ...​na1​​>ny1​​n(n−1)a1​y1​​>n(n−1)y1​y2​​n(n−1)(n−2)a1​y1​y2​​>n(n−1)(n−2)y1​y2​y3​​n(n−1)...(n−m+2)a1​y1​y2​...ym−2​​>n(n−1)...(n−m+2)y1​y2​y3​...ym−1​​n(n−1)...(n−m+1)a1​y1​y2​...ym−2​ym−1​​=n(n−1)...(n−m+1)y1​y2​y3​...ym−1​a1​​​...​⟹p1′​>p1​⟹p1′​p2′​>p1​p2​⟹p1′​p2′​p3′​>p1​p2​p3​⟹p1′​p2′​...pm−1′​>p1​p2​...pm−1​⟹p1′​p2′​...pm−1′​pm′​=p1​p2​...pm−1​pm​​(12) 即前 m − 1 m-1 m−1项都是 E b a s e ′ ( X ) \mathbb{E}_{\rm base}'(X) Ebase′​(X)严格地大于 E b a s e ′ ( X ) \mathbb{E}_{\rm base}'(X) Ebase′​(X)中的对应项，最后一项括号外的部分完全相等。

  于是有： E b a s e ′ ( X ) > E b a s e ( X ) (13) \mathbb{E}_{\rm base}'(X)>\mathbb{E}_{\rm base}(X)\tag{13} Ebase′​(X)>Ebase​(X)(13)

综上所述，上面的证明论述了这样的一个事实：

• 对于猜测序列 G G G，只要它在当次猜测时没有选取此时集合 U U U中包含数量最多的那种元素，那我们总是可以重新构造一个新的猜测序列 G ′ G' G′满足当次猜测时选取此时集合 U U U中包含数量最多的那种元素（即把该元素直接调换到序列开头），并且利用 G ′ G' G′序列进行猜测的猜对次数的数学期望比 G G G严格地大。这样就说明了每次猜测集合 U U U中包含数量最多的那种元素是最优策略。

Q.E.D. ■ \text{Q.E.D.}\blacksquare Q.E.D.■

定理 2 2 2 的证明并不十分复杂，结论也很符合直觉，但是事情还远远没有结束。

考虑这样一个场景：你已经用知己知彼查看了一名其他角色的手牌，然后你有办法随机拆掉该角色手牌中的一张，你会选择去拆吗？

1. 比如你看到的是手牌中只有一种花色，如果选择去拆，那么期望严格地会减一，所以不会有小笨蛋去拆。

2. 比如现在你知己知彼看到的是 { ♠ , ♠ , ♥ } \{♠,♠,♥\} { ♠,♠,♥}，即 { 1 , 1 , 2 } \{1,1,2\} { 1,1,2}：

   • 如果选择不拆，那么期望盗书成功的次数就是 4 / 3 4/3 4/3；（自行计算检验）

   • 如果选择去拆，有 1 / 3 1/3 1/3的概率拆中♥，皆大欢喜，盗书成功的次数就是 2 2 2；有 2 / 3 2/3 2/3的概率拆中 ♠ ♠ ♠，这就比较惨，盗书成功条件期望下降为 1 1 1；总的来说，期望盗书成功的次数还是 4 / 3 4/3 4/3，期望不变；

3. 再比如现在你知己知彼看到的是 { ♠ , ♠ , ♥ , ♥ , ♣ } \{♠,♠,♥,♥,♣\} { ♠,♠,♥,♥,♣}，即 { 1 , 1 , 2 , 2 , 3 } \{1,1,2,2,3\} { 1,1,2,2,3}：

   • 如果选择不拆，那么期望盗书成功的次数是 11 / 15 11/15 11/15；（ 1.1 1.1 1.1节中已经计算过）
   • 如果选择去拆，那么期望盗书成功的次数是 9 / 10 9/10 9/10，期望大大提升；（自行计算检验）

那么到底过河拆桥到底值不值得去使用呢？笔者通过代码仿真（仿真代码见本文第 4 4 4节）发现，竟然除了单一花色的情况，所有仿真结果都显示先拆一张牌再进行盗书，总是不会降低期望盗书成功地次数！ 即有下面定理的成立：

定理 3 3 3（使用一张过河拆桥总是更优的选择）：

已知可重集（即可以包含重复元素的集合） U = { x 1 , x 2 , . . . , x n } U=\{x_1,x_2,...,x_n\} U={ x1​,x2​,...,xn​}中包含 n n n个元素，其中 x i ∈ { 1 , 2 , . . . , k } , i = 1 , 2 , . . . , n x_i\in\{1,2,...,k\},i=1,2,...,n xi​∈{ 1,2,...,k},i=1,2,...,n。从 U U U中不放回地依次采样一个元素，并猜测本次采样得到的元素对应的数值，直到猜测错误为止。

令上述过程中猜测正确的次数为 X X X，定义使用定理 2 2 2 中的最优策略进行猜测得到的 X X X的数学期望为 f ( U ) f(U) f(U)，随机从 U U U中去除一个元素后再使用定理 2 2 2 中的最优策略进行猜测得到的 X X X的数学期望为 g ( U ) g(U) g(U)，若 k ≥ 2 k\ge 2 k≥2（非单一花色），且假定每种取值（即 1 , 2 , . . . , k 1,2,...,k 1,2,...,k）在 U U U至少存在一个元素与之对应。则必然有： f ( U ) ≤ g ( U ) (14) f(U)\le g(U)\tag{14} f(U)≤g(U)(14)

接下来笔者将严格证明定理 3 3 3 的正确性：

证明：立体数学归纳法（我觉得这个名称特别适合这个证明的形式）。

这里还是先定义 a i a_i ai​（ i = 1 , 2 , . . . , k i=1,2,...,k i=1,2,...,k）表示 U U U中取值为 i i i的元素数量（即每种花色对应的手牌数量），不妨设 a 1 ≥ a 2 ≥ . . . ≥ a k ≥ 1 a_1\ge a_2\ge...\ge a_k\ge1 a1​≥a2​≥...≥ak​≥1

定义 h ( a 1 , a 2 , . . . , a k ) h(a_1,a_2,...,a_k) h(a1​,a2​,...,ak​)表示 U U U在最优策略下的期望盗书成功次数（ X X X的期望），即最大盗书成功次数。

根据条件期望的知识，我们有： h ( a 1 , a 2 , . . . , a k ) = a 1 a 1 + a 2 + . . . + a k ( h ( a 1 − 1 , a 2 , . . . , a k ) + 1 ) (15) h(a_1,a_2,...,a_k)=\frac{a_1}{a_1+a_2+...+a_k}(h(a_1-1,a_2,...,a_k)+1)\tag{15} h(a1​,a2​,...,ak​)=a1​+a2​+...+ak​a1​​(h(a1​−1,a2​,...,ak​)+1)(15) 式 ( 15 ) (15) (15)显然是正确的，注意式 ( 15 ) (15) (15)非常的重要，这将是下面数学归纳法的根基所在。

• 考察 k = 2 k=2 k=2的情况，即手牌只包含两种花色的情况： f ( U ) = h ( a 1 , a 2 ) = a 1 a 1 + a 2 ( h ( a 1 − 1 , a 2 ) + 1 ) g ( U ) = a 1 a 1 + a 2 h ( a 1 − 1 , a 2 ) + a 2 a 1 + a 2 h ( a 1 , a 2 − 1 ) (16) f(U)=h(a_1,a_2)=\frac{a_1}{a_1+a_2}(h(a_1-1,a_2)+1)\\ g(U)=\frac{a_1}{a_1+a_2}h(a_1-1,a_2)+\frac{a_2}{a_1+a_2}h(a_1,a_2-1)\tag{16} f(U)=h(a1​,a2​)=a1​+a2​a1​​(h(a1​−1,a2​)+1)g(U)=a1​+a2​a1​​h(a1​−1,a2​)+a1​+a2​a2​​h(a1​,a2​−1)(16) 其中 g ( U ) g(U) g(U)的第一项表示拆到了取值为 1 1 1的元素，第二项表示拆到了取值为 2 2 2的元素。则等价证明推导： f ( U ) ≤ g ( U ) ⟺ a 1 a 1 + a 2 ( h ( a 1 − 1 , a 2 ) + 1 ) ≤ a 1 a 1 + a 2 h ( a 1 − 1 , a 2 ) + a 2 a 1 + a 2 h ( a 1 , a 2 − 1 ) ⟺ h ( a 1 , a 2 − 1 ) ≥ a 1 a 2 (17) \begin{aligned} f(U)\le g(U)&\Longleftrightarrow\frac{a_1}{a_1+a_2}(h(a_1-1,a_2)+1)\le\frac{a_1}{a_1+a_2}h(a_1-1,a_2)+\frac{a_2}{a_1+a_2}h(a_1,a_2-1)\\ &\Longleftrightarrow h(a_1,a_2-1)\ge\frac{a_1}{a_2} \end{aligned}\tag{17} f(U)≤g(U)​⟺a1​+a2​a1​​(h(a1​−1,a2​)+1)≤a1​+a2​a1​​h(a1​−1,a2​)+a1​+a2​a2​​h(a1​,a2​−1)⟺h(a1​,a2​−1)≥a2​a1​​​(17) 即等价于证明 h ( a 1 , a 2 − 1 ) ≥ a 1 / a 2 h(a_1,a_2-1)\ge a_1/a_2 h(a1​,a2​−1)≥a1​/a2​，做差量代换 a 1 = a 2 + t a_1=a_2+t a1​=a2​+t，其中 t ≥ 0 t\ge 0 t≥0

  先考察 a 1 = a 2 a_1=a_2 a1​=a2​的情形（ t = 0 t=0 t=0），即证明 h ( a 2 , a 2 − 1 ) ≥ 1 h(a_2,a_2-1)\ge 1 h(a2​,a2​−1)≥1，基于如下的观察： h ( 1 , 1 ) = 1 ⟹ h ( 1 , 2 ) = h ( 2 , 1 ) = 2 3 ( h ( 1 , 1 ) + 1 ) = 4 3 > 1 ⟹ h ( 2 , 2 ) = 2 4 ( h ( 1 , 2 ) + 1 ) > 1 2 ( 1 + 1 ) = 1 ⟹ h ( 2 , 3 ) = h ( 3 , 2 ) = 3 5 ( h ( 2 , 2 ) + 1 ) > 3 5 ( 1 + 1 ) > 1 ⟹ h ( 3 , 3 ) = 3 6 ( h ( 2 , 3 ) + 1 ) > 1 2 ( 1 + 1 ) = 1 . . . ⟹ h ( a 2 − 1 , a 2 − 1 ) > 1 ⟹ h ( a 2 , a 2 − 1 ) = a 2 2 a 2 − 1 ( h ( a 2 − 1 , a 2 − 1 ) + 1 ) > 2 a 2 2 a 2 − 1 > 1 (18) \begin{aligned} h(1,1)=1&\Longrightarrow h(1,2)=h(2,1)=\frac23(h(1,1)+1)=\frac43>1\\ &\Longrightarrow h(2,2)=\frac{2}{4}(h(1,2)+1)>\frac12(1+1)=1\\ &\Longrightarrow h(2,3)=h(3,2)=\frac{3}{5}(h(2,2)+1)>\frac35(1+1)>1\\ &\Longrightarrow h(3,3)=\frac{3}{6}(h(2,3)+1)>\frac12(1+1)=1\\ &...\\ &\Longrightarrow h(a_2-1,a_2-1)>1\\ &\Longrightarrow h(a_2,a_2-1)=\frac{a_2}{2a_2-1}(h(a_2-1,a_2-1)+1)>\frac{2a_2}{2a_2-1}>1 \end{aligned}\tag{18} h(1,1)=1​⟹h(1,2)=h(2,1)=32​(h(1,1)+1)=34​>1⟹h(2,2)=42​(h(1,2)+1)>21​(1+1)=1⟹h(2,3)=h(3,2)=53​(h(2,2)+1)>53​(1+1)>1⟹h(3,3)=63​(h(2,3)+1)>21​(1+1)=1...⟹h(a2​−1,a2​−1)>1⟹h(a2​,a2​−1)=2a2​−1a2​​(h(a2​−1,a2​−1)+1)>2a2​−12a2​​>1​(18) 式 ( 18 ) (18) (18)中的推导本质上是数学归纳法，这样我们就证明了任意的 a 2 a_2 a2​，都有 h ( a 2 , a 2 − 1 ) > 1 h(a_2,a_2-1)>1 h(a2​,a2​−1)>1

  那么再从 h ( a 2 , a 2 − 1 ) h(a_2,a_2-1) h(a2​,a2​−1)作为起点，类似地可以归纳到 h ( a 2 + t , a 2 − 1 ) h(a_2+t,a_2-1) h(a2​+t,a2​−1)： h ( a 2 + t , a 2 − 1 ) = a 2 + t 2 a 2 + t − 1 ( h ( a 2 + t − 1 , a 2 − 1 ) + 1 ) ≥ a 2 + t 2 a 2 + t − 1 ( a 2 + t − 1 a 2 + 1 ) = a 2 + t a 2 (19) h(a_2+t,a_2-1)=\frac{a_2+t}{2a_2+t-1}(h(a_2+t-1,a_2-1)+1)\ge\frac{a_2+t}{2a_2+t-1}\left(\frac{a_2+t-1}{a_2}+1\right)=\frac{a_2+t}{a_2}\tag{19} h(a2​+t,a2​−1)=2a2​+t−1a2​+t​(h(a2​+t−1,a2​−1)+1)≥2a2​+t−1a2​+t​(a2​a2​+t−1​+1)=a2​a2​+t​(19) 式 ( 19 ) (19) (19)中的 ≥ \ge ≥号使用的是已知 ( h ( a 2 + t − 1 , a 2 − 1 ) + 1 ) ≥ ( a 2 + t − 1 ) / a 2 (h(a_2+t-1,a_2-1)+1)\ge (a_2+t-1)/a_2 (h(a2​+t−1,a2​−1)+1)≥(a2​+t−1)/a2​的归纳结果。

  于是 h ( a 1 , a 2 − 1 ) ≥ a 1 / a 2 h(a_1,a_2-1)\ge a_1/a_2 h(a1​,a2​−1)≥a1​/a2​总是成立，根据式 ( 17 ) (17) (17)，可知 k = 2 k=2 k=2时定理 3 3 3 成立。

• 接下来考察 k > 2 k>2 k>2的情况：

f ( U ) = h ( a 1 , a 2 , . . . , a k ) = a 1 ∑ i = 1 k a i ( h ( a 1 − 1 , a 2 , . . . , a k ) + 1 ) g ( U ) = a 1 ∑ i = 1 k a i h ( a 1 − 1 , a 2 , . . . , a k ) + a 2 ∑ i = 1 k a i h ( a 1 , a 2 − 1 , . . . , a k ) + . . . + a k ∑ i = 1 k a i h ( a 1 , a 2 , . . . , a k − 1 ) (20) f(U)=h(a_1,a_2,...,a_k)=\frac{a_1}{\sum_{i=1}^k a_i}(h(a_1-1,a_2,...,a_k)+1)\\ g(U)=\frac{a_1}{\sum_{i=1}^k a_i}h(a_1-1,a_2,...,a_k)+\frac{a_2}{\sum_{i=1}^k a_i}h(a_1,a_2-1,...,a_k)+...+\frac{a_k}{\sum_{i=1}^k a_i}h(a_1,a_2,...,a_{k}-1)\tag{20} f(U)=h(a1​,a2​,...,ak​)=∑i=1k​ai​a1​​(h(a1​−1,a2​,...,ak​)+1)g(U)=∑i=1k​ai​a1​​h(a1​−1,a2​,...,ak​)+∑i=1k​ai​a2​​h(a1​,a2​−1,...,ak​)+...+∑i=1k​ai​ak​​h(a1​,a2​,...,ak​−1)(20)

类似式 ( 17 ) (17) (17)作等价证明代换： f ( U ) ≤ g ( U ) ⟺ a 2 h ( a 1 , a 2 − 1 , . . . , a k ) + . . . + a k h ( a 1 , a 2 , . . . , a k − 1 ) ≥ a 1 (21) \begin{aligned} f(U)\le g(U)&\Longleftrightarrow a_2h(a_1,a_2-1,...,a_k)+...+a_kh(a_1,a_2,...,a_{k}-1)\ge a_1 \end{aligned}\tag{21} f(U)≤g(U)​⟺a2​h(a1​,a2​−1,...,ak​)+...+ak​h(a1​,a2​,...,ak​−1)≥a1​​(21) 看起来式 ( 21 ) (21) (21)比式 ( 17 ) (17) (17)要复杂不少，但证明思路是完全一样的，也是使用双重数学归纳：

• 首先说明 f ( 1 , 1 , . . . , 1 ) ≥ 1 / ( k − 1 ) f(1,1,...,1)\ge 1/(k-1) f(1,1,...,1)≥1/(k−1)成立。（括号中有 k k k个 1 1 1，以 f ( 1 , 1 ) = 1 f(1,1)=1 f(1,1)=1为基，利用式 ( 15 ) (15) (15)直接数学归纳易证）

• 接下来类似式 ( 18 ) (18) (18)，推出在 a 1 = a 2 = . . . = a k a_1=a_2=...=a_k a1​=a2​=...=ak​的情况下，式 ( 21 ) (21) (21)成立，即有： f ( a k , a k , . . . , a k − 1 ) ≥ 1 k − 1 (22) f(a_k,a_k,...,a_k-1)\ge\frac{1}{k-1}\tag{22} f(ak​,ak​,...,ak​−1)≥k−11​(22) 注意为什么式 ( 18 ) (18) (18)能够一路推下来，是因为每次推导括号外的乘数必然大于 1 / 2 1/2 1/2，这里类似地乘数必然大于 1 / k 1/k 1/k，因此可以递推归纳。

• 最后做类似式 ( 19 ) (19) (19)的归纳证明，得到任意的 a 1 ≥ a 2 ≥ . . . ≥ a k a_1\ge a_2\ge ...\ge a_k a1​≥a2​≥...≥ak​都使得式 ( 21 ) (21) (21)的结论成立：

  这个归纳太长，限于篇幅我就不写了，简单地说需要先固定 a 2 , . . . , a k a_2,...,a_k a2​,...,ak​来归纳 a 1 a_1 a1​，然后固定 a 3 , . . . , a k a_3,...,a_k a3​,...,ak​归纳 a 2 a_2 a2​，以此类推直到归纳完 a k a_k ak​，这也就是为什么称这个证明叫立体数学归纳法。

Q.E.D. ■ \text{Q.E.D.}\blacksquare Q.E.D.■

定理 3 3 3 揭示了一个非常重要地性质，这意味着在已知别人手牌花色的情况下，先拆别人一张牌总是更优，当然如果你有更多地拆顺，只要别人手牌花色不一，每打出一张拆顺都会使得盗书成功的期望次数更高。

这其实是有些反直觉的，有些人可能会想当然地认为先拆只会让盗书的上限下降（因为对方手牌变少了），怎么会提升期望收益呢？

那么这里就衍生出一个新问题：蒋干难道一定要先拆吗？我能不能先盗书若干次再去拆？

比如在例子 U = { 1 , 1 , 2 } U=\{1,1,2\} U={ 1,1,2}中，很多人可能就会觉得我可以先猜一个 1 1 1（成功率 2 / 3 2/3 2/3），如果猜中了再去拆就能确保盗书中最后一张牌，这似乎看起来也挺合理的。

然而下面的定理将会告诉你，先盗后拆总是比先拆后盗要劣的，因此就不要耍小聪明了，老老实实地先打过河拆桥吧。

定理 4 4 4（先盗后拆 v.s. 先拆后盗）:

在定理 3 3 3 的条件下，先猜一次（按照最优策略），再随机删除的做法总是比直接拆得到的猜中次数的数学期望更低。

证明：这个证明相比于前面的证明都要更加简单。

为了方便描述，还是先考虑 k = 2 k=2 k=2即两花色的情况，并假定 a 1 > a 2 a_1>a_2 a1​>a2​（ a 1 = a 2 a_1=a_2 a1​=a2​的情况是类似的推导）：

• 先盗后拆： e 1 = a 1 a 1 + a 2 ( a 1 − 1 a 1 + a 2 − 1 h ( a 1 − 2 , a 2 ) + a 2 a 1 + a 2 − 1 h ( a 1 − 1 , a 2 − 1 ) + 1 ) (23) e_1 = \frac{a_1}{a_1+a_2}\left(\frac{a_1-1}{a_1+a_2-1}h(a_1-2,a_2)+\frac{a_2}{a_1+a_2-1}h(a_1-1,a_2-1)+1\right)\tag{23} e1​=a1​+a2​a1​​(a1​+a2​−1a1​−1​h(a1​−2,a2​)+a1​+a2​−1a2​​h(a1​−1,a2​−1)+1)(23)

• 先拆后盗： e 2 = a 1 a 1 + a 2 h ( a 1 − 1 , a 2 ) + a 2 a 1 + a 2 h ( a 1 , a 2 − 1 ) = a 1 a 1 + a 2 ⋅ a 1 − 1 a 1 + a 2 − 1 ( h ( a 1 − 2 , a 2 ) + 1 ) + a 2 a 1 + a 2 ⋅ a 1 a 1 + a 2 − 1 ( h ( a 1 − 1 , a 2 − 1 ) + 1 ) (24) \begin{aligned} e_2&=\frac{a_1}{a_1+a_2}h(a_1-1,a_2)+\frac{a_2}{a_1+a_2}h(a_1,a_2-1)\\ &=\frac{a_1}{a_1+a_2}\cdot\frac{a_1-1}{a_1+a_2-1}(h(a_1-2,a_2)+1)+\frac{a_2}{a_1+a_2}\cdot\frac{a_1}{a_1+a_2-1}(h(a_1-1,a_2-1)+1) \end{aligned}\tag{24} e2​​=a1​+a2​a1​​h(a1​−1,a2​)+a1​+a2​a2​​h(a1​,a2​−1)=a1​+a2​a1​​⋅a1​+a2​−1a1​−1​(h(a1​−2,a2​)+1)+a1​+a2​a2​​⋅a1​+a2​−1a1​​(h(a1​−1,a2​−1)+1)​(24)

我们要说明 e 1 ≤ e 2 e_1\le e_2 e1​≤e2​，注意到式 ( 23 ) (23) (23)与式 ( 24 ) (24) (24)中所有包含 h ( ⋅ , ⋅ ) h(\cdot,\cdot) h(⋅,⋅)的项刚好都完全匹配，因此可以消去，这等价于： e 1 ≤ e 2 ⟺ a 1 a 1 + a 2 ≤ a 1 ( a 1 − 1 ) + a 1 a 2 ( a 1 + a 2 ) ( a 1 + a 2 − 1 ) ⟺ a 1 a 1 + a 2 ≤ a 1 a 1 + a 2 (25) \begin{aligned} e_1\le e_2&\Longleftrightarrow\frac{a_1}{a_1+a_2}\le\frac{a_1(a_1-1)+a_1a_2}{(a_1+a_2)(a_1+a_2-1)}\\ &\Longleftrightarrow\frac{a_1}{a_1+a_2}\le \frac{a_1}{a_1+a_2} \end{aligned}\tag{25} e1​≤e2​​⟺a1​+a2​a1​​≤(a1​+a2​)(a1​+a2​−1)a1​(a1​−1)+a1​a2​​⟺a1​+a2​a1​​≤a1​+a2​a1​​​(25) 式 ( 25 ) (25) (25)其实是说明，在花色只有两种的情况下，只要两种花色的手牌数量不等，那么先盗后拆与先拆后盗对期望是没有区别的，但是如果你用类似的思路去推导 a 1 = a 2 a_1=a_2 a1​=a2​的情况，就会发现先盗后拆总是比先拆后盗要显著地差，具体推导如下：

e 1 = 1 2 ( a 2 − 1 2 a 2 − 1 h ( a 2 − 2 , a 2 ) + a 2 2 a 2 − 1 h ( a 2 − 1 , a 2 − 1 ) + 1 ) e 2 = 1 2 h ( a 2 − 1 , a 2 ) + 1 2 h ( a 2 , a 2 − 1 ) = h ( a 2 , a 2 − 1 ) = a 2 2 a 2 − 1 ( h ( a 2 − 1 , a 2 − 1 ) + 1 ) (26) e_1 = \frac12\left(\frac{a_2-1}{2a_2-1}h(a_2-2,a_2)+\frac{a_2}{2a_2-1}h(a_2-1,a_2-1)+1\right)\\ e_2=\frac12h(a_2-1,a_2)+\frac12h(a_2,a_2-1)=h(a_2,a_2-1)=\frac{a_2}{2a_2-1}(h(a_2-1,a_2-1)+1)\tag{26} e1​=21​(2a2​−1a2​−1​h(a2​−2,a2​)+2a2​−1a2​​h(a2​−1,a2​−1)+1)e2​=21​h(a2​−1,a2​)+21​h(a2​,a2​−1)=h(a2​,a2​−1)=2a2​−1a2​​(h(a2​−1,a2​−1)+1)(26)

等价变换有： e 1 ≤ e 2 ⟺ ( a 2 − 1 ) h ( a 2 − 2 , a 2 ) − 1 ≤ a 2 h ( a 2 − 1 , a 2 − 1 ) ⟺ a 2 ( a 2 − 1 ) 2 a 2 − 2 ( h ( a 2 − 2 , a 2 − 1 ) + 1 ) − 1 ≤ a 2 ( a 2 − 1 ) 2 a 2 − 2 ( h ( a 2 − 2 , a 2 − 1 ) + 1 ) ⟺ − 1 ≤ 0 (27) \begin{aligned} e_1\le e_2&\Longleftrightarrow (a_2-1)h(a_2-2,a_2)-1\le a_2h(a_2-1,a_2-1)\\ &\Longleftrightarrow\frac{a_2(a_2-1)}{2a_2-2}(h(a_2-2,a_2-1)+1)-1\le \frac{a_2(a_2-1)}{2a_2-2}(h(a_2-2,a_2-1)+1)\\ &\Longleftrightarrow -1\le 0 \end{aligned}\tag{27} e1​≤e2​​⟺(a2​−1)h(a2​−2,a2​)−1≤a2​h(a2​−1,a2​−1)⟺2a2​−2a2​(a2​−1)​(h(a2​−2,a2​−1)+1)−1≤2a2​−2a2​(a2​−1)​(h(a2​−2,a2​−1)+1)⟺−1≤0​(27)

因此在 a 1 = a 2 a_1=a_2 a1​=a2​时，不等号严格成立。

类似地可以推广到 k ≥ 3 k\ge 3 k≥3的情况，此时结论是完全一致的：

• 若 a 1 > a 2 a_1>a_2 a1​>a2​，先盗后拆与先拆后盗从期望上来看没有区别。

• 若 a 1 = a 2 a_1=a_2 a1​=a2​，则先盗后拆显著地比先拆后盗的期望猜对正确次数更低。

有兴趣地朋友可以自己推导。

Q.E.D. ■ \text{Q.E.D.}\blacksquare Q.E.D.■

本文着重研究蒋干通过知己知彼或其他手段洞悉其他玩家全部手牌花色的情况下，不同的场景下应当采取何种策略进行盗书，具体的结论与推论有：

1. 盗书的最优策略总是猜测对方手牌中花色最多（或之一）的花色。（定理 2 2 2）
2. 如果有办法破坏对方手牌，那么除非已知对方手牌中只剩一种花色，就一定是先破坏完对方的手牌，再进行盗书。（定理 3 3 3）
3. 先拆后盗与先盗后拆在占优花色唯一的情况下，盗书成功次数的期望是完全相同的，若占优花色不止一种，则先盗后拆比先拆后盗要严格地差。（定理 4 4 4）

其实关于蒋干盗书的问题点还有很多，比如若只知道对方手牌中一部分牌的花色，最优策略是怎样的？个人感觉结论应该与上面三条是一致的，但是证明应该是比较复杂的。

另外，还有一个问题点就是如何针对蒋干来调整手牌，很多人都知道应该让花色更散，比如四种花色的数量序列 [ 1 , 1 , 1 , 1 ] [1,1,1,1] [1,1,1,1]当然要比 [ 2 , 2 , 0 , 0 ] [2,2,0,0] [2,2,0,0]更难猜，但是你能一下子说出 [ 2 , 3 , 3 , 3 ] [2,3,3,3] [2,3,3,3]与 [ 2 , 2 , 2 , 3 ] [2,2,2,3] [2,2,2,3]哪个更难猜吗（即比较 h ( 3 , 3 , 3 , 2 ) h(3,3,3,2) h(3,3,3,2)与 h ( 3 , 2 , 2 , 2 ) h(3,2,2,2) h(3,2,2,2)的大小）？其实这就很困难。

这就牵扯到 h ( a 1 , . . . , a k ) h(a_1,...,a_k) h(a1​,...,ak​)函数的性质究竟是怎么样的，它的单调性与收敛性如何，这些都留给后人去探讨吧。

下面的代码是笔者用于实验仿真使用，大部分结论都是先通过仿真确定其正确性，再加以理论证明。

# -*- coding: utf-8 -*-
# @author: caoyang
# @email: caoyang@163.sufe.edu.cn
# 蒋干盗书

import random

EPSILON = 1e-8

# 生成参数
def generate_kwargs_for_color_list(color_list):
	total_cards = sum(color_list)										# 卡牌总数
	total_colors = len(color_list)										# 花色总数
	sorted_remained_color_list = sorted(color_list, reverse=True)		# 降序排列的各花色卡牌数
	return { 
        'total_cards'				: total_cards,
			'total_colors'				: total_colors,
			'sorted_remained_color_list': sorted_remained_color_list}	

# 给定每种花色的卡牌数量, 计算偷对次数的数学期望
def get_expected_correct_guess(color_list, **kwargs):
	if not len(kwargs):
		kwargs = generate_kwargs_for_color_list(color_list=color_list)
	
	# 计算辅助分布列与分布列
	auxiliary_distribution_series = get_auxiliary_distribution_series(color_list=color_list, **kwargs)
	distribution_series = get_distribution_series(color_list=color_list, auxiliary_distribution_series=auxiliary_distribution_series, **kwargs)
	
	# 计算数学期望: 两种方法
	# 1 根据辅助分布列计算数学期望
	def _expectation_by_auxiliary_distribution_series(_auxiliary_distribution_series):	
		_expectation = 0.
		_temp = 1.
		for _auxiliary_probability in _auxiliary_distribution_series:
			_temp *= _auxiliary_probability
			_expectation += _temp
		return _expectation		
	expectation_1 = _expectation_by_auxiliary_distribution_series(_auxiliary_distribution_series=auxiliary_distribution_series)
	
	# 2 根据分布列计算数学期望
	def _expection_by_distribution_series(_distribution_series):
		_expectation = 0.
		for i in range(len(_distribution_series)):
			_expectation += i * distribution_series[i]	
		return 	_expectation
	expectation_2 = _expection_by_distribution_series(_distribution_series=distribution_series)
	
	# 检验正确性
	assert abs(expectation_1 - expectation_2) < EPSILON
	
	return expectation_1

# 上面函数的简约形式: 不计算分布列, 直接使用辅助分布列
def easy_get_expected_correct_guess(color_list, **kwargs):
	if len(kwargs):
		kwargs = generate_kwargs_for_color_list(color_list=color_list)
	auxiliary_distribution_series = get_auxiliary_distribution_series(color_list=color_list, **kwargs)
	def _expectation_by_auxiliary_distribution_series(_auxiliary_distribution_series):	
		_expectation = 0.
		_temp = 1.
		for _auxiliary_probability in _auxiliary_distribution_series:
			_temp *= _auxiliary_probability
			_expectation += _temp
		return _expectation		
	expectation = _expectation_by_auxiliary_distribution_series(_auxiliary_distribution_series=auxiliary_distribution_series)
	return expectation

# 只计算辅助分布列
def get_auxiliary_distribution_series(color_list, **kwargs):
	if len(kwargs):
		total_cards = kwargs['total_cards']
		total_colors = kwargs['total_colors']
		sorted_remained_color_list = kwargs['sorted_remained_color_list'][:]
	else:
		total_cards = sum(color_list)									# 卡牌总数
		total_colors = len(color_list)									# 花色总数
		sorted_remained_color_list = sorted(color_list, reverse=True)	# 降序排列的各花色卡牌数

	auxiliary_distribution_series = []
	for i in range(total_cards):
		auxiliary_probability = sorted_remained_color_list[0] / (total_cards - i)
		auxiliary_distribution_series.append(auxiliary_probability)
		sorted_remained_color_list[0] -= 1
		sorted_remained_color_list.sort(reverse=True)
	assert auxiliary_distribution_series[-1] == 1.
	return auxiliary_distribution_series
	
# 只计算分布列
def get_distribution_series(color_list, auxiliary_distribution_series, **kwargs):
	if len(kwargs):
		total_cards = kwargs['total_cards']
		total_colors = kwargs['total_colors']
	else:
		total_cards = sum(color_list)									# 卡牌总数
		total_colors = len(color_list)									# 花色总数
		
	distribution_series = []
	temp = 1.
	for i in range(total_cards + 1):
		if i < total_cards:
			probability = temp * (1 - auxiliary_distribution_series[i])
			temp *= auxiliary_distribution_series[i]
		else:
			probability = temp * auxiliary_distribution_series[-1]
		distribution_series.append(probability)
	return distribution_series

# 随机删除若干张卡牌之后再删除
def get_expected_correct_guess_after_deleting(color_list, n_delete=1):
	
	assert n_delete == 1, NotImplemented
	
	total_cards = sum(color_list)
	color_lists_after_deleting = []
	probabilitys_of_color_lists_after_deleting = []
	expectations_of_color_lists_after_deleting = []
	
	for i in range(len(color_list)):
		if color_list[i] >= n_delete:
			color_list_after_deleting = color_list[:]
			color_list_after_deleting[i] -= 1
			color_lists_after_deleting.append(color_list_after_deleting)
			probabilitys_of_color_lists_after_deleting.append(color_list[i] / total_cards)
			expectations_of_color_lists_after_deleting.append(easy_get_expected_correct_guess(color_list=color_list_after_deleting))
	expectation = 0.
	for _probability, _expectation in zip(probabilitys_of_color_lists_after_deleting, expectations_of_color_lists_after_deleting):
		expectation += _probability * _expectation
	return expectation
	
# 先做若干次猜测后再随机删除若干张卡牌
def get_expected_correct_guess_after_deleting_and_preguess(color_list, n_guess, n_delete=1):
	
	assert n_delete == 1, NotImplemented
	
	# 退化情况
	if n_guess == 0:
		return get_expected_correct_guess_after_deleting(color_list=color_list, n_delete=n_delete)
	
	total_cards = sum(color_list)										# 卡牌总数
	total_colors = len(color_list)										# 花色总数
	sorted_remained_color_list = sorted(color_list, reverse=True)		# 降序排列的各花色卡牌数
	
	auxiliary_probabilitys = []
	
	for i in range(n_guess):
		auxiliary_probability = sorted_remained_color_list[0] / (total_cards - i)
		auxiliary_probabilitys.append(auxiliary_probability)
		sorted_remained_color_list[0] -= 1
		sorted_remained_color_list.sort(reverse=True)
	
	expectation = get_expected_correct_guess_after_deleting(color_list=sorted_remained_color_list[:], n_delete=1)
	for auxiliary_probability in auxiliary_probabilitys[::-1]:
		expectation = (auxiliary_probability * (expectation + 1))
	return expectation
	
# 去掉一张牌是否期望上总是增加偷对的张数？（花色不一时似乎总是正确的）
def test_1():
	N = 100000
	count = 0
	for _ in range(N):
		print(_, count)
		color_list = [random.randint(2, 1000) for i in range(4)]
		e1 = easy_get_expected_correct_guess(color_list=color_list)
		e2 = get_expected_correct_guess_after_deleting(color_list=color_list, n_delete=1)
		if e2 > e1 - EPSILON:
			count += 1
	print(count)

# 去掉一张牌是否总是增加偷对的张数？（并不是，但大概率是对的）
def test_2():
	N = 100000
	count = 0
	for _ in range(N):
		color_list = [random.randint(2, 100) for i in range(2)]
		e1 = easy_get_expected_correct_guess(color_list=color_list)
		color_list[0] -= 1
		e2 = get_expected_correct_guess_after_deleting(color_list=color_list, n_delete=1)
		if e2 > e1:
			count += 1
	print(count)
	

# 直接去掉一张牌是否期望上比先猜一张牌再去掉一张牌更好（似乎总是正确的）
def test_3():
	N = 100000
	count1 = 0
	count2 = 0
	for _ in range(N):
		
		color_list = [random.randint(2, 100) for i in range(4)]
		e1 = get_expected_correct_guess_after_deleting(color_list=color_list, n_delete=1)
		e2 = get_expected_correct_guess_after_deleting_and_preguess(color_list=color_list, n_guess=1, n_delete=1)
		if e1 > e2 - EPSILON:
			count1 += 1
		
		elif e1 < e2 + EPSILON:
			count2 += 1
		
		print(_, count1, count2, e1, e2)
	
	
# 一些特殊的规律总结
def test_4():
	print(get_expected_correct_guess(color_list=[100]))
	print(get_expected_correct_guess(color_list=[100, 100]))
	print(get_expected_correct_guess(color_list=[100, 100, 100]))
	print(get_expected_correct_guess(color_list=[100, 100, 100, 100]))
	print(get_expected_correct_guess(color_list=[100, 100, 100, 100, 100]))
	print(get_expected_correct_guess(color_list=[100, 100, 100, 100, 100]))
	
	print('-' * 64)
	
	print(get_expected_correct_guess(color_list=[3, 3, 3, 3]))
	print(get_expected_correct_guess(color_list=[3, 3, 3, 4]))
	print(get_expected_correct_guess(color_list=[3, 4, 4, 4]))
	print(get_expected_correct_guess(color_list=[4, 4, 4, 4]))
	
	print('-' * 64)
	
	print(get_expected_correct_guess(color_list=[3, 5]))
	print(get_expected_correct_guess(color_list=[300, 500]), 500 / 301)
	
	print('-' * 64)
	
	print(get_expected_correct_guess(color_list=[2, 98]))
	print(get_expected_correct_guess(color_list=[1, 98]))
	print(get_expected_correct_guess(color_list=[2, 97]))
	print(get_expected_correct_guess(color_list=[2, 97]) * 0.98 + get_expected_correct_guess(color_list=[1, 98]) * 0.02)
	print(get_expected_correct_guess(color_list=[2, 97]) * 0.98 + 0.98)
	print('-' * 64)
	print(get_expected_correct_guess(color_list=[1, 99]))
	print(get_expected_correct_guess(color_list=[0, 99]))
	print(get_expected_correct_guess(color_list=[1, 98]))
	print(get_expected_correct_guess(color_list=[1, 98]) * 0.99 + get_expected_correct_guess(color_list=[0, 99]) * 0.01)
	print(get_expected_correct_guess(color_list=[1, 98]) * 0.99 + 0.99)
	
# easy方法正确性保证
def test_5():
	N = 100000
	count = 0
	for _ in range(N):
		print(_, count)
		color_list = [random.randint(2, 1000) for i in range(4)]
		e1 = get_expected_correct_guess(color_list=color_list)
		e2 = easy_get_expected_correct_guess(color_list=color_list)
		if abs(e1 - e2) <= EPSILON:
			count += 1
	print(count)

if __name__ == '__main__':
	b = 1000
	color_list = [1,1,1]
	e1 = easy_get_expected_correct_guess(color_list=color_list)
	e2 = get_expected_correct_guess_after_deleting(color_list=color_list)
	print(e1)
	print(e2)

最后以一盘李典蒋干两牌一血翻盘几乎是满状态的四个一线蜀团的对局作为本文的完结（虽然只是一把演武，但是还是挺精彩的，足以证明李典蒋干的恐怖上限）：