關(guān)于“猜數(shù)字”游戲的一點(diǎn)討論

2023-09-22 03:54 作者:再見李華 0人讀過 | 我要投稿

引言

一個經(jīng)典的數(shù)字游戲：

????????出題人從1至100選一個整數(shù)，讓答題人猜。答題人每次猜一個整數(shù)，隨后出題人將給出猜得偏大、偏小或是猜中了的結(jié)果。若沒猜中，答題人根據(jù)出題人的偏大偏小提示繼續(xù)猜。

????????突發(fā)奇想：

“猜數(shù)字”游戲里最多需要幾次能確保猜中？
多少次以內(nèi)猜中的概率過半？

基本假設(shè)

出題人隨機(jī)選擇數(shù)字，被選中的數(shù)字在選擇范圍內(nèi)均勻分布。

討論

????????首先是答題人怎么猜這個問題。答題人希望使用盡可能少的次數(shù)猜出出題人選擇的數(shù)字。筆者參考文章《用信息論玩猜數(shù)字》https://zhuanlan.zhihu.com/p/473658388 ，確定使用“猜中間”的猜法，即每次都猜已知范圍內(nèi)中間的那一個數(shù)字。

????????受限于筆者能力，此處假設(shè)每一次猜的時候，范圍內(nèi)都有中間的一個數(shù)字。例如范圍1至3則猜2，范圍1至5則猜3。

????????注意到一個很特殊的情況，如果已知要猜的數(shù)在1至3之間（不包括1和3），那么就可以確定那個數(shù)是2，只需一次即可猜中。在范圍更大的情況里，如上文所述，假設(shè)每一次猜的范圍內(nèi)都有中間的一個數(shù)，在猜的次數(shù)最多的情況下，最終都會變成類似1至3之間猜2的這種情況。例如1至9內(nèi)猜5，猜得偏大，1至5內(nèi)猜3，猜得偏小，3至5內(nèi)猜4。

????? ? 基于上述過程建立模型。要猜的數(shù)為x，已知A<x<B。在像1至3內(nèi)猜2這種最后一次猜數(shù)中，B-A=2，即可一次猜中。像1至5內(nèi)猜3這種倒數(shù)第二次猜數(shù)中，B-A=4。以此類推，記W=B-A。推出在倒數(shù)第n次猜數(shù)中

$W%3D2%5En$

????????下面考慮猜中數(shù)字需要的次數(shù)n的概率分布p(n)。第一次就猜中的概率很容易得出。由于選數(shù)是均勻分布的，A<x<B的范圍內(nèi)有W-1個整數(shù)，所以

$p(1)%3D%5Cfrac%7B1%7D%7BW-1%7D%20$

????????進(jìn)一步，如果這次沒猜中，進(jìn)入下一次。直到這次才猜中的概率等于前幾次都沒猜中的概率乘上縮小后的范圍內(nèi)猜一個數(shù)猜中的概率

????????編寫計算程序。

????????當(dāng)W=128時

$%5Clog_2%20128%3D7$

????????最多7次即可猜中數(shù)字。

????????此時繪制概率分布與累計概率圖

????????可以得知，在W=128時，使用“猜中間”的方法可以確保7次內(nèi)一定猜中，6次內(nèi)猜中的概率接近而不足0.5。

????????改變W的值，綜合如下。

????????可以發(fā)現(xiàn)一件非常有趣的事。在最多需要n次一定能猜中的情況下，在n-1次內(nèi)猜中的概率隨著W的增加而增加，且似乎以0.5為界。表中當(dāng)最多需要14次一定能猜中的情況下，13次內(nèi)猜中的概率舍入小數(shù)點(diǎn)后四位的結(jié)果已經(jīng)是0.5。

????????此外，把n_max=14這一情況單獨(dú)拿出來看。

$p(n%3C%3D13)%5Capprox%200.5$

$p(n%3C%3D12)%5Capprox%200.25$

$p(n%3C%3D11)%5Capprox%200.125$

????????看上面三個數(shù)字很容易聯(lián)想到1/2，1/4，1/8。于是筆者進(jìn)行了一個對比。

????????可以發(fā)現(xiàn)累計概率非常像是一個公比為2的等比數(shù)列?；蛟S可以大膽猜想，當(dāng)n_max足夠大，即W足夠大時，累積概率近似為等比數(shù)列。即n_max次內(nèi)猜中的概率為1，n_max-1次內(nèi)猜中的概率接近而不足為0.5，n_max-2次內(nèi)猜中的概率接近而不足為0.25，等等。

結(jié)論

用“猜中間”的方法猜數(shù)所需的最多次數(shù)隨著猜數(shù)范圍的增大而增大。且在比所需最多次數(shù)少一次以內(nèi)猜中的概率隨猜數(shù)范圍的增大逐漸接近0.5。
舉例來說，1至63（包括1和63）范圍內(nèi)猜數(shù)，最多需要6次即可猜中，5次以內(nèi)猜中的概率約為0.4921。1至127（包括1和127）范圍內(nèi)猜數(shù)，最多需要7次即可猜中，6次以內(nèi)猜中的概率約為0.4961。
一個更典型的范圍是1至100（包括1和100）范圍內(nèi)猜數(shù)，最多需要7次即可猜中，5次內(nèi)猜中的概率不足0.5。
當(dāng)猜數(shù)的范圍足夠大時，n次內(nèi)猜中的概率近似為公比為2的等比數(shù)列。
舉例來說，1至16383（包括1和16383）范圍內(nèi)猜數(shù)，最多需要14次，13次以內(nèi)猜中的概率約為且不足0.5，12次以內(nèi)猜中的概率約為且不足0.25，11次以內(nèi)猜中的概率約為且不足0.125，等等。