有多少人参加考试

mathe

5道题目10个人总共5种不同的结果: { 00000 10000 21110 22101 20211 21021 21202 22012 20122 22220 } { 00000 11000 20100 12010 20201 12021 20212 12122 02222 21222 } { 00000 11000 20110 12101 20021 02211 12012 20202 12220 02122 } { 00000 11000 20110 12101 20021 02211 12012 20202 12220 21122 } { 00000 11000 20110 12101 20021 02211 12012 21211 20202 12220 }

mathe

现在我们有条件来证明6道题目的时候14个人不行. 如果14个人可以,我们首先挑选最后一道题目选择答案较多的那些人,至少有10个人. 将这不少于10个人去掉最后一道题目,那么必然等价于上面5种答案中的一种. 所以我们只需要将上面的这几个方案都先添加一题,每题的答案要么是0,要么是1(而且其中0和1的数目都不小于4,共672种可能). 那么我们总共得到672*5=3360个不同的10个人6道题的搜索起点.对于每一个,我们穷举能否继续添加4个人.搜索结果全部失败,说明6道题目最多13个人.

mathe

而6道题13个人的答案计算机还在搜索中,现在已经找到两个不同的答案: { 000000 111000 210100 020011 112110 020102 012201 021121 102121 120220 201212 112022 222021 } { 000000 111000 200110 120101 112011 210201 102102 201121 012121 102220 210022 021212 222020 } 而如果我们能够先将5道题目9个以上的人的所有答案先搜索出来,然后类似前面的方法去添加4个人,应该可以更加快的得出结果. 由于现在的程序已经能够穷举5道题目的情况,我估计用这种方法应该可以解决7道题目的问题.

mathe

现在我们得到这个序列的前6项: 3,4,6,9,10,12 这个在 http://www.research.att.com/~njas/sequences/ 上还没有收集,谁来提交一下?

nlrte13

000000 000111 001012 120222 102021 022210 110211 212102 220020 011020 201211 121201 121120 000000 101100 101211 110202 202202 201022 120220 220112 021212 122010 211010 012121 220001 000000 011100 011211 101202 022212 202001 202112 002022 120121 221000 210212 211220 112010 000000 011100 011211 101202 022212 202001 202112 002022 120121 221000 210212 211220 112010

mathe

你这是完全列表吗?还有置换下等价的是不是过滤了?

mathe

发现程序算完了. 13个的结果只有3个: { 000000 111000 210100 020011 112110 020102 012201 021121 102121 120220 201212 112022 222021 } { 000000 111000 200110 120101 112011 210201 102102 201121 012121 102220 210022 021212 222020 } { 000000 111000 210110 021101 210021 021012 120211 201211 012211 222000 021220 210202 102122 }

nlrte13

最后一条粘贴了两次 - -# 其实就是三条。。。

mathe

不错,你是如何计算的? 主要是等价的数据是如何淘汰的

nlrte13

剪枝，限界^^