愚妄——如果想在 10 道中对上 7 道

· · 算法·理论

问题不十分大，但很细。

有 10 道没有题面的判断题。A 和 B 在俩小黑屋中，只能和主持人对话。主持人首先告诉 A 这 10 题按顺序的答案，接着对于每道题，两人各自告诉主持人自己的选择，主持人再告诉两人正确答案与对方的选择，之后方可回答下一题。若两人的选择均与正确答案相同，称此题“答对了”。假设 A 与 B 被关进小黑屋前已经约定好了策略，求在任意情况下至少答对 7 题的策略。

不妨拓展一下，假使试图在 n 题中对的题尽可能多，该怎么办？

设 f_{n,m} 表示在 n 题中对至少 m 题的情况下答案集合的最大大小，此处 n,m\in\N 且 m\le n。

于是可以写出转移：

f_{n,m}\le \begin{cases} 2^n&m=0\\ \min\{2^{n-1},f_{n-1,m-1}+f_{n-1,m}\}+\min\{2^{n-1},2f_{n-1,m}\}&0<m<n\\ 1&m=n \end{cases}.

为何是“\le”呢？因为这只是一个上界而已。（就我个人而言，我压根不知道如何构造方案逼近该上界。）

但显然如果 f_{n,m}<2^n，则根本不存在策略满足任意情况下 n 题对 m 题。而计算可知 f_{10,7}\le934<2^{10}。所以 10 道根本对不了 7 道嘛！

（之后供题人就被我们联合声讨了，严肃反省之后改成了 9 对 6。）

将上面转移中的“f”替换为“g”，“\le”替换为“=”，然后考虑一下上界 g_{n,m} 的性质。

那么会首先注意到如下几点：

由此可以预见其存在两条分界线对应两个 \min 的临界值。

然而事情没这么简单，不妨写个代码看看前几个 g 的取值：（这里为了方便写的 GNU C）

g[15][15],i,j;
#define min(x,y)({int a=(x),b=(y);(a<b?a:b);})
main()
{
    for(i=0;i<15;i++)
    {
        g[i][0]=1<<i,g[i][i]=1;
        for(j=1;j<i;j++)
            g[i][j]=min(1<<i-1,g[i-1][j-1]+g[i-1][j])+min(1<<i-1,g[i-1][j]<<1);
        for(j=0;j<i;j++)
            if(g[i][j]==1<<i)
                printf("-\t");
            else
                printf("%d\t",g[i][j]);
        puts(i?"1":"-");
    }
}

只看见了一条分界线。（其实中间并非没有，仔细看能看见一个 94 一个 1590 等。）

为何会如此呢？

答案也十分显然：分界线左侧都是指数级增长的，而右侧却是多项式级别增长的，因此两条分界线中间的区域几乎不存在，才只能看见一条分界线。

分界线右侧的多项式如下：

:-:|:-:|:-: $0$|$1$|$\binom n0 1$|$3n-3$|$3\binom n1-3\binom n0 2$||$9\binom n2-9\binom n1-32\binom n0 3$||$27\binom n3-27\binom n2-96\binom n1-324\binom n0 4$||$81\binom n4-81\binom n3-288\binom n2-972\binom n1-3808\binom n0 5$||$243\binom n5-243\binom n4-864\binom n3-2916\binom n2-11424\binom n1+3782\binom n0

暂时还看不出规律。

不过很容易可以看出这个错误数量的量级大概是 \sqrt n。

这实在是令人汗颜。因为这比某乎上一些人求出的低很多。

剩下的待会也不再写。