愚妄——如果想在 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}

的性质。

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

$1\le g_{n,m}\le2^n$ ；
$m<n$ 时 $g_{n,m}>g_{n,m+1}$ ；
$g_{n,m}<g_{n+1,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

等。）

为何会如此呢？

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

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

$n-m$	普通幂	下降幂
$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

。

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

剩下的待会再写。

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

文章操作

相关推荐

评论

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