十道四选一题目，通过总分反馈蒙最少次数保证满分

毒酒滴冻鸭

这道题是在百度贴吧数学吧前几天出现的一道原创题目，原帖子在这里，后来有人转发到智力题吧这个帖子。

这里我再尝试写一个比较严谨的设定好了：



你被困在中东某一个战乱国家，现在正在想办法回国，而唯一方法是参与一个共有十道选择题的考试并获得满分来证明自己是良好公民不是间谍。

考试题目是以阿拉伯文发问的，而你对这种语文一窍不通，所以只能靠蒙答案来作答。

考试形式是这样：你在一个密室里的电脑屏幕会看到十道选择题，每道题有四个选项，其中只有一个为正确答案。

你在点击十个选项（不能留空不答）后确认提交，然后系统只会显示你的总分（每题答对得一分，答错零分），但是你完全不会知道哪几道题答对，哪几道题答错。

如果不能获得满分，你可以选择重来，然后屏幕会重新显示这十道题目（题目内容完全一样，连每题的四个选项次序也是固定不变）。你再作答然后再提交，再看总分。

但是困境在这里：你在进入密室之前必须事先付款购买你能提交答案的次数，每次100美刀。比如你付了1000美刀买得十次提交答案的机会，然后十次都不能获得满分，那么就丧失了考试资格，要永远被困在这个国家。

所以你在参与考试之前，首先必须先设计好一个方案，用最少的答题次数保证无论运气如何背，最终也必定能获得满分，然后付款购买这些次数并参与考试。



那么要保证成功的最低成本是多少呢？原帖子的42楼有两位高手合作下设计了一个15次（1500美刀）的解法，我待会在楼下再描述一下。然后有两个扩展思路：

一、如果是m道题，每题有n个选项又如何？

二、如果规则允许可以在某些题目留空不答而提交答案，可否再进一步优化解法？

毒酒滴冻鸭

15次能保证成功的解法：



一、首先前三次答题每题都答同一选项（分别为【十个a】、【十个b】、【十个c】），那么三次下来就可以统计出十个正确答案里分别各出现了多少次【a、b、c、d】，并把这四个选项按出现次数排序，从多到少分别改称为【W、X、Y、Z】。

假设f(e)为选项e出现的次数，则有：【f(W) + f(X) + f(Y) + f(Z) = 10】和【f(W) ≥ f(X) ≥ f(Y) ≥ f(Z)】。

每个f(e)的数值上限为10，下限为0。但是【f(W)】不能小于3，否则【f(W) + f(X) + f(Y) + f(Z)】的最大值为2+2+2+2=8小于10。同时【f(W) + f(X)】不能小于6，否则【f(X)】最大值为2而【f(Y)】最小值为3，违反了【f(X) ≥ f(Y)】。如此得出：【f(Y) + f(Z) ≤ 4】。

（当【f(W) + f(X) = 6】时，【f(W) + f(X) + f(Y) + f(Z)】只能是以下三种情况之一：【3+3+3+1】、【3+3+2+2】、【4+2+2+2】。）



二、现在咱们要用九次答题来确定所有【W】和【X】的出现位置。首先默认这九次答题里全部十道题都答【W】，除了在第一至九题其中一题改答【X】。

正常情况下答【十个W】的总分应该是【f(W)】，但是这里因为咱们有一题改答了【X】，所以会出现三种不同结果：
——如果该题的正确答案是【W】而咱们答了【X】，那么总分就会变成【f(W)-1】。
——如果该题的正确答案是【X】而咱们答了【X】，那么总分就会变成【f(W)+1】。
——如果该题的正确答案是【Y或Z】而咱们答了【X】，那么总分会保持为【f(W)】。

如此九次答题后咱们可以确定第一至九题有哪些正确答案为【W】和【X】。再配合之前的统计结果，可以判断第十题的正确答案是【W】、【X】、还是【Y或Z】。



三、最后咱们要用最多三次答题把剩下来最多四题的【Y或Z】也判断出来并获得满分。注意从这里开始所有正确答案为【W或X】的题目咱们都必定能答对，也必须要答对。

首先如果【f(Z) = 0】，那么剩下来的题目全部答【Y】就能得到满分。所以咱们只需要考虑【f(Z) ≥ 1】的情况，则【f(Y) + f(Z)】只有以下四种不同情况：【1+1】、【2+1】、【3+1】、【2+2】。咱们逐一探讨：

【1+1】：咱们已确定了八道【W或X】的正确答案，剩下最后两道【Y或Z】，只能是【Y、Z】或【Z、Y】两种次序，两次答题就能保证满分！

【2+1】：咱们已确定了七道【W或X】的正确答案，剩下最后三道【Y或Z】，只能是【Y、Y、Z】、【Y、Z、Y】或【Z、Y、Y】三种次序，三次答题就能保证满分！

【3+1】：咱们已确定了六道【W或X】的正确答案，剩下最后四道【Y或Z】，只能是【Y、Y、Y、Z】、【Y、Y、Z、Y】、【Y、Z、Y、Y】、【Z、Y、Y、Y】四种次序。咱们先答一次【Y、Y、Z、Z】，则根据四种次序可以得到【f(W)+f(X)+3】、【f(W)+f(X)+1】两种总分（每种总分对应两种次序），如此再两次答题就能保证满分！

【2+2】：咱们已确定了六道【W或X】的正确答案，剩下最后四道【Y或Z】，只能是【Y、Y、Z、Z】、【Y、Z、Y、Z】、【Y、Z、Z、Y】、【Z、Y、Y、Z】、【Z、Y、Z、Y】、【Z、Z、Y、Y】六种次序。咱们先答一次【Y、Z、W、W】，则根据六种次序可以得到【f(W)+f(X)+2】、【f(W)+f(X)+1】、【f(W)+f(X)】三种总分（每种总分对应两种次序），如此再两次答题就能保证满分！



综上所述，最多只需要3+9+3=15次答题，咱们就能保证获得满分。（不排除有其他更优秀的方案可以利用14次或更少的答题也能保证获得满分！）

毒酒滴冻鸭

一组两道四选一，测四次必能确定答案，第五次保证满分。

【解法】
前三次分别测【aa】、【bb】、【cc】，确定【a,b,c,d】的出现次数。
如果格式是【AA】（2），则直接确定答案！
如果格式是【AB】（1+1），则有【AB/BA】两种次序，再测一次必能确定答案！

毒酒滴冻鸭

一组三道四选一，测五次必能确定答案，第六次保证满分。

【解法】
前三次分别测【aaa】、【bbb】、【ccc】，确定【a,b,c,d】的出现次数。
如果格式是【AAA】（3），则直接确定答案！
如果格式是【AAB】（2+1），则有【AAB/ABA/BAA】三种次序；第四次测【ABC】，分别得【1/2/0】分，直接确定答案！
如果格式是【ABC】（1+1+1），则有【ABC/ACB/BAC/BCA/CAB/CBA】六种次序；第四次测【AAB】，分别得【1/2/1/0/2/0】分，每种分数对应两种次序，测第五次必能确定答案！

毒酒滴冻鸭

一组四道四选一，测六次必能确定答案，第七次保证满分。

【解法】
前三次分别测【aaaa】、【bbbb】、【cccc】，确定【a,b,c,d】的出现次数。

如果格式是【AAAA】（4），则直接确定答案！

如果格式是【AAAB】（3+1），则有【AAAB/AABA/ABAA/BAAA】四种次序；第四次测【AABB】，分别得【3/3/1/1】分，每种分数对应两种次序，测第五次必能确定答案！

如果格式是【AABB】（2+2），则有【AABB/ABAB/ABBA/BAAB/BABA/BBAA】六种次序；第四次测【ABCC】，分别得【1/2/2/0/0/1】分，每种分数对应两种次序，测第五次必能确定答案！

如果格式是【AABC】（2+1+1），则有十二种次序：
AABC / ABAC / ABCA / BAAC / BACA / BCAA
AACB / ACAB / ACBA / CAAB / CABA / CBAA
第四次测【AABB】，分别得分：
3 / 1 / 1 / 1 / 1 / 0
3 / 2 / 2 / 2 / 2 / 0
如果得分是【0】或【3】，每种分数对应两种次序，测第五次必能确定答案！
如果得分是【1】，则有【ABAC/ABCA/BAAC/BACA】四种次序；第五次测【ABAB】，分别得【3/2/1/0】分，直接确定答案！
如果得分是【2】，则有【ACAB/ACBA/CAAB/CABA】四种次序；第五次测【ACAC】，分别得【3/2/1/0】分，直接确定答案！

如果格式是【ABCD】（1+1+1+1），则有廿四种次序：
ABCD / ABDC / ACBD / ACDB / ADBC / ADCB
BACD / BADC / BCAD / BCDA / BDAC / BDCA
CABD / CADB / CBAD / CBDA / CDAB / CDBA
DABC / DACB / DBAC / DBCA / DCAB / DCBA
第四次测【AABB】，分别得分：
1 / 1 / 2 / 2 / 2 / 2
1 / 1 / 0 / 0 / 0 / 0
2 / 2 / 0 / 0 / 1 / 1
2 / 2 / 0 / 0 / 1 / 1
如果得分是【0】，则有【BCAD/BCDA/BDAC/BDCA/CBAD/CBDA/DBAC/DBCA】八种次序；第五次测【BCAC】，分别得【3/2/3/1/1/0/2/0】分，每种分数对应两种次序，测第六次必能确定答案！
如果得分是【2】，则有【ACBD/ACDB/ADBC/ADCB/CABD/CADB/DABC/DACB】八种次序；第五次测【ACBC】，分别得【3/2/3/1/1/0/2/0】分，每种分数对应两种次序，测第六次必能确定答案！
如果得分是【1】，则有【ABCD/ABDC/BACD/BADC/CDAB/CDBA/DCAB/DCBA】八种次序；第五次测【ABCB】，分别得【3/2/1/0/1/0/1/0】分：
——如得【3】或【2】分，直接确定答案！
——如得【1】分，则有【BACD/CDAB/DCAB】三种次序，第六次测【DCAB】，分别得【0/2/4】分，直接确定答案！
——如得【0】分，则有【BADC/CDBA/DCBA】三种次序，第六次测【DCBA】，分别得【0/2/4】分，直接确定答案！

毒酒滴冻鸭

暂时先这样，【一组五道四选一】估计是【测七次必能确定答案，第八次保证满分】，但是穷举的过程更复杂，将来有空再做。

根据上述三种分组，【十道四选一】分割成【4+3+3】的话，需要【6+5+5+1】=【17】次才能保证满分；分割成【4+4+2】则也需要【6+6+4+1】=【17】次才能保证满分；总之都及不上二楼的【15】次解法。。。

王守恩

毒酒滴冻鸭 发表于 2021-12-30 08:09
15次能保证成功的解法：

怪自己太笨，憋了好几天，又不敢问。2楼还是没看懂。
二、现在咱们要用九次答题来确定所有【W】和【X】的出现位置。
九次答题可以确定6道题？没看懂。譬如：
10道四选一，测15次必能确保满分。正确答案: AABBCDDCBA

我们不妨先这样约定(最坏打算):
答题顺序:ABCD。先确定A,再确定B,确定C,确定D,
01道四选一，测04次必能确保满分。正确答案: D
02道四选一，测05次必能确保满分。正确答案: DC
03道四选一，测06次必能确保满分。正确答案: DCB
04道四选一，测07次必能确保满分。正确答案: DCBA
05道四选一，测09次必能确保满分。正确答案: ADCBA
06道四选一，测10次必能确保满分。正确答案: ABDCBA
07道四选一，测11次必能确保满分。正确答案: ABCDCBA
08道四选一，测12次必能确保满分。正确答案: ABCDDCBA
09道四选一，测14次必能确保满分。正确答案: AABCDDCBA
10道四选一，测15次必能确保满分。正确答案: AABBCDDCBA
11道四选一，测16次必能确保满分。正确答案: AABBCCDDCBA
12道四选一，测17次必能确保满分。正确答案: AABBCCDDDCBA

毒酒滴冻鸭

王守恩 发表于 2022-1-3 18:12
怪自己太笨，憋了好几天，又不敢问。2楼还是没看懂。
二、现在咱们要用九次答题来确定所有【W】和【X】 ...

因为你漏了看【第一部分】解法的头三次测试，所以没有好好理解整个解法的精粹。

根据你的例子【AABBCDDCBA】，在第一至三次测试后，确定了十道题目有【三个A】、【三个B】、【两个C】、【两个D】。

【第二部分】的九次测试，分别提交：
04.【BAAAAAAAAA】得2分
05.【ABAAAAAAAA】得2分
06.【AABAAAAAAA】得4分
07.【AAABAAAAAA】得4分
08.【AAAABAAAAA】得3分
09.【AAAAABAAAA】得3分
10.【AAAAAABAAA】得3分
11.【AAAAAAABAA】得3分
12.【AAAAAAAABA】得4分

至此确定第【01、02】题答案为【A】，第【03、04、09】题答案为【B】，第【05、06、07、08】题答案为【C或D】，再根据【第一部分】的统计结果，判断出第【10】题答案为【A】。

最后在【第三部分】，使用两次测试确定出第【05、06、07、08】题的答案次序是【CDDC】，最后用第15次提交【AABBCDDCBA】得到满分！

王守恩

毒酒滴冻鸭 发表于 2022-1-3 20:37
因为你漏了看【第一部分】解法的头三次测试，所以没有好好理解整个解法的精粹。

根据你的例子【AABB ...

谢谢 毒酒滴冻鸭 网友！看懂了，好像是这样。
00.【AABBCDDCBA】
04.【BAAAAAAAAA】得2分
05.【ABAAAAAAAA】得2分
06.【AABAAAAAAA】得4分
07.【AAABAAAAAA】得4分
08.【AAAABAAAAA】得3分
09.【AAAAABAAAA】得3分
10.【AAAAAABAAA】得3分
11.【AAAAAAABAA】得3分
12.【AAAAAAAABA】得4分
也就是说，2分表示答案是A，4分表示答案是B，3分表示答案是CD。
当然，第1行标准答案：00.【AABBCDDCBA】可以随意换。
但是，9次合计不会变，只有3种可能：
2分*2次+4分*3次+3分*4次，
2分*3次+4分*3次+3分*3次，
2分*3次+4分*2次+3分*4次，
【第一部分】还是看懂的，没问题。
对7楼再说明一下
10道四选一，测15次必能确保满分。正确答案: AABBCDDCBA
正确答案3+3+2+2是最坏打算
我们不妨这样约定正确答案: 3=A,3=B,2=C,2=D
这样约定(缩小范围)，后面的诉述可能会方便些。
类似的，我们这样约定
答题顺序:ABCD。先确定A,再确定B,确定C,确定D,
01道四选一，测04次必能确保满分。正确答案: D
02道四选一，测05次必能确保满分。正确答案: DC
03道四选一，测06次必能确保满分。正确答案: DCB
04道四选一，测07次必能确保满分。正确答案: DCBA
05道四选一，测09次必能确保满分。正确答案: ADCBA
06道四选一，测10次必能确保满分。正确答案: ABDCBA
07道四选一，测11次必能确保满分。正确答案: ABCDCBA
08道四选一，测12次必能确保满分。正确答案: ABCDDCBA
09道四选一，测14次必能确保满分。正确答案: AABCDDCBA
10道四选一，测15次必能确保满分。正确答案: AABBCDDCBA
11道四选一，测16次必能确保满分。正确答案: AABBCCDDCBA
12道四选一，测17次必能确保满分。正确答案: AABBCCDDDCBA