趣题:尽可能用奇数次猜测完成猜数游戏

    现在,我在心里想一个不超过n的正整数t。你的任务是尽可能用奇数次猜测猜中这个数(你知道n是多少)。每次猜测后,我都会告诉你你所做的猜测是大了还是小了。你不能猜测已经被排除了的数(来消耗猜测次数),你的每次猜测都必须符合我原来给出的回答。你觉得,你获胜(奇数次猜中)的几率有多大?

 
    动态规划的几个类似的经典模型启发了我们:设a[m]表示采取最优策略后在m个数里猜奇数次猜中的概率,b[m]表示如果题目要求我们猜偶数次,那最优策略下有m个数时获胜的概率是多少。考虑现在我有m个数可以猜,我想在奇数次内猜中。现在我猜的是数字i。狗屎运最好时,我一次猜中直接就赢了,它的概率是1/m;有(i-1)/m的情况下我会得到“大了”的提示,这样的话我需要用偶数次猜测去猜前面那i-1个数;剩余的那(m-i)/m的情况中,我需要用偶数次猜测去猜m-i个数。因此,a[m] = Max {1/m + (i-1)/m * b[i-1] + (m-i)/m * b[m-i], 1≤i≤m} 。类似地,我们也可以得出b[m]的递推公式:b[m] = Max {(i-1)/m * a[i-1] + (m-i)/m * a[m-i], 1≤i≤m} 。
    学习使用Mathematica确实是一件好事,你可以用Mathematica非常方便地描述出我们上面的两个递推公式,不需要自己去写那些冗长的程序了。
a[m_] := Max[Table[1/m + (i-1)/m * b[i-1] + (m-i)/m * b[m-i], {i, m}]]; a[0] := 0;
b[m_] := Max[Table[(i-1)/m * a[i-1] + (m-i)/m * a[m-i], {i, m}]]; b[0] := 0;


    让我们看一看结果怎么样:
In[3]:= Table[a[i], {i, 12}]
Out[3]= {1, 1/2, 2/3, 3/4, 3/5, 2/3, 5/7, 5/8, 2/3, 7/10, 7/11, 2/3}

In[4]:= Table[b[i], {i, 12}]
Out[4]= {0, 1/2, 2/3, 1/2, 3/5, 2/3, 4/7, 5/8, 2/3, 3/5, 7/11, 2/3}

    猛然一看似乎看不出规律,但稍微把数列重新整理一下,规律一下子就出来了:
a[i] = {1, 1/2, 2/3, 3/4, 3/5, 4/6, 5/7, 5/8, 6/9, 7/10, 7/11, 8/12}
b[i] = {0, 1/2, 2/3, 2/4, 3/5, 4/6, 4/7, 5/8, 6/9, 6/10, 7/11, 8/12}

    我们开始猜想,是不是a[m] = [(2m+1)/3] / m,b[m] = [2m/3] / m啊? (我这里用[]表示取下整)
    只需要注意到[x]+[y] ≤ [x+y]始终成立,简单的数学归纳法可以立即得出这一结论:

a[m] = 1/m + (i-1)/m * b[i-1] + (m-i)/m * b[m-i]
    = 1/m + (i-1)/m * [2(i-1)/3]/(i-1) + (m-i)/m * [2(m-i)/3]/(m-i)
    = 1/m + [2(i-1)/3]/m + [2(m-i)/3]/m
    = (1 + [2(i-1)/3] + [2(m-i)/3]) / m
    ≤ [(2m+1)/3] / m

b[m] = (i-1)/m * a[i-1] + (m-i)/m * a[m-i]
    = (i-1)/m * [(2i-1)/3]/(i-1) + (m-i)/m * [(2m-2i+1)/3]/(m-i)
    = [(2i-1)/3]/m + [(2m-2i+1)/3]/m
    = ([(2i-1)/3] + [(2m-2i+1)/3]) / m
    ≤ [2m/3] / m

    什么情况下[x]+[y] ≤ [x+y]能够取到等号呢?显然,如果x和y中有一个恰为整数时,等号一定成立。当i=1时,a[m]一式可以取到等号,因为此时2(i-1)/3是一个整数;同样地,i=2时b[m]一式也能取等号,因为此时(2i-1)/3为整数。i的取值告诉了我们游戏的最佳策略:按顺序依次猜1, 3, 4, 6, 7, 9, …。这样的话,只有对方想的数恰好是3的倍数时才会以偶数次猜测结束游戏:如果对方想的数除以3余1,我们将在第奇数次说到这个数;如果对方想的数除以3余2,我们将在第偶数次得到一个“猜大了”的提示,然后再猜一次得到答案。采取这种策略,获胜的概率显然是[(2m+1)/3]/m,也即大约为2/3。

5 条评论

发表评论