数学的一点小问题

mathcoder23

问题一： 现在有 2 道选择题，每道选择题仅有一个正确选项（ 4 个选项），选择正确得一分，否则不得分。 选完 2 道题后，可以查看得到的分数，问：如果设计出选择方案，通过最小查看得到分数次数，得到 2 道选择题的正确答案，这个最小查看得到分数次数是多少？
问题二： 将上诉的 2 道选择题换成 50 道，求最小次数？
这类题的本质是什么原理？有没有什么推广的定理？

aimisiyou

这让我想到以前玩的一个数字游戏，随机生成一个四位数（星号隐藏），然后如果你随意输入一个四位数，返回结果为mAnB形式，其中m代表有m个数位置和数字都是对的，n代表有n个数是对的但位置不对,游戏只给8次机会让你猜，8次是否一定可以猜出该四位数？如该四位数为1234，若你猜成4321，返回结果为0A4B;若你猜成3214，返回结果为2A2B,如果你猜成5678，返回结果显示0A0B。也就是当你完全猜对时，返回结果为4A0B.

KeyTo9_Fans

要求的 “次数” 通常有两种定义：

1、平均次数
例如：有1/2的概率需要1次，1/2的概率需要3次，平均次数就是2次。

2、最坏情况下的次数
例如：有1/2的概率需要1次，1/2的概率需要3次，最坏情况下的次数就是3次。

如果是平均次数，那么我们有：

平均次数 = 初始不确定度 / 平均每次询问得到的不确定度

如果是最坏情况下的次数，那么我们有：

最大次数 = 初始不确定度 / 每次询问得到的最低不确定度

不确定度是用信息论里的“熵”来度量的。

通常情况下，不同的询问得到的熵不同。

至于如何询问才能得到最大的熵，则需要枚举所有可能的情况，才能找出最佳的询问方案。

mathcoder23

KeyTo9_Fans 发表于 2016-6-15 15:00
要求的 “次数” 通常有两种定义：

1、平均次数

至于如何询问才能得到最大的熵，则需要枚举所有可能的情况，才能找出最佳的询问方案。
这个最佳方案一定枚举才行吗？
我计算过两道两个选项的最坏判断次数是2
两道四个选项的最坏判断次数是4
在两道两个选项过渡到两道四个选项的过程中我明显感觉到了其中有迭代的现象，现在就是不知如何求解。解得通式。

KeyTo9_Fans

定理$1$：$1$道题$m$个选项的最坏询问次数是$(m-1)$。

证明：

每次询问至少可以排除$1$个选项，当选项剩下$1$个的时候即得正确答案，因此最坏询问次数是$(m-1)$。

定理$2$：当$m>1$时，$2$道题$m$个选项的最坏询问次数是$m$。

证明：

易得$2$道题$2$个选项的最坏询问次数是$2$。

假设$m$个选项的最坏询问次数是$m$，只需证明$(m+1)$个选项的最坏询问次数是$(m+1)$。

当选项个数为$(m+1)$时，第$1$次询问任意答案，

如果得分为$2$，则直接得到正确答案；

如果得分为$0$，则选项个数只剩$m$个，再询问不超过$m$次即得正确答案，总的询问次数不超过$(m+1)$。

如果得分为$1$，那么第$2$次询问时，将第$1$道题的答案改一下，得到新的得分。

如果新的得分为$2$，则直接得到正确答案；

如果新的得分为$0$，则说明之前是第$1$道题答对了，并且现在第$2$道题只剩下$m$个选项，再询问不超过$(m-1)$次即得正确答案，总的询问次数不超过$(m+1)$。

如果新的得分为$1$，则说明是第$2$道题答对了，并且第$1$道题只剩下$(m-1)$个选项，再询问不超过$(m-2)$次即得正确答案，总的询问次数不超过$m$。

综上所述，当$m$个选项的最坏询问次数是$m$时，$(m+1)$个选项的最坏询问次数是$(m+1)$。

根据数学归纳法可得定理$2$对于所有的$m>1$都成立。

#####

当题目数量大于$2$时，情况比较复杂，期待继续探索。