一道智力题

Sirius

小明非常聪明，但对英语一窍不通。有一天，老师出了5道英语选择题，每题有4个选择，只有一个正确答案。
同学们都桉要求（每题只选一个答案）做完试卷

（5题都做了）后交给了老师，老师只在答卷上给出成绩分数（每题1分）。

问题：假如没有两张答卷是雷同的，小明要看多少张批完的考卷后，肯定能得满分？

王守恩

没有两张雷同的答卷，那么最多有考卷1024张。

zeroieme

不失一般性，假设第一题正确的答案是A。
倒霉的小明看到的试卷第一题全是选B或者C。于是小明不知道第一题正确答案是A还是D。
第一题选B或者C，2选1。后面4选1。总共有\(2*4^4=512\)。再多一张与前面不同的试卷，就是张513试卷，小明才能了解全部答案。

Sirius

能保证得满分，感觉最少应该看到的不同试卷数应该不到290，不知有没有巧妙的算法

zeroieme

Sirius 发表于 2017-6-8 21:37
能保证得满分，感觉最少应该看到的不同试卷数应该不到290，不知有没有巧妙的算法

最少情况是看的第一张刚好满分的。讨论最多（最倒霉）才有意义。

Sirius

能保证得满分，当然是考虑到最极端的情况

Sirius

第一题全是B或C的所有不同试卷有2乘以4的4次方，即512份试卷（假设第一题答案是A或D），但要肯定知道第2, 3, 4, 5题的答案不需512份试卷，应该少很多。

zeroieme

Sirius 发表于 2017-6-8 22:53
第一题全是B或C的所有不同试卷有2乘以4的4次方，即512份试卷（假设第一题答案是A或D），但要肯定知道第2, 3, 4, 5 ...

现在小明是看批完的考卷，而不是自己为试错而反复做卷。也就是试卷作为一个黑箱模型，小明不能控制输入，只是作为旁观者看别人的输入与输出。别人的输入应当看作随机的。

Sirius

是看试卷，不是自己有意识的做很多试卷，如果是后者，答案还会小些。

王守恩

zeroieme 发表于 2017-6-8 22:44
最少情况是看的第一张刚好满分的。讨论最多（最倒霉）才有意义。

倒霉的小明，给了他32张答卷，连1道题也没“猜”出来。
1，22222=0
2，22223=0
3，22232=0
4，22233=0
5，22322=0
6，22323=0
7，22332=0
8，22333=0
9，23222=0
10，23223=0
11，23232=0
12，23233=0
13，23322=0
14，23323=0
15，23332=0
16，23333=0
17，32222=0
18，32223=0
19，32232=0
20，32233=0
21，32322=0
22，32323=0
23，32332=0
24，32333=0
25，33222=0
26，33223=0
27，33232=0
28，33233=0
29，33322=0
30，33323=0
31，33332=0
32，33333=0
说明：用1，2，3，4表示A，B，C，D