有多少人参加考试

东邪

试卷上有6道选择题，每题有3个选项（单选题，且不允许不选），结果阅卷老师发现，在所有卷子中任选3张答卷，都有一道题的选择互不相同，请问最多有多少人参加了这次考试？ （互不相同是指的完全不相同，即正好包括1、2、3三种答案。） 转自天涯

风云剑

感觉难度很大

shshsh_0510

2# 风云剑 是复杂呢。感觉应该是19吧

shshsh_0510

这个比我想象的还复杂，我想了两天也没想通，太浪费时间了，决定先放弃，等有时间再想。 说说目前结果吧。网上有好多答13的，不好说对不对，但至少我看到的证明都说的不清不楚的 一个容易得到的上界是19，开始我猜可以达到，但费了半天劲也没构造出来，甚至连13的也没做出！ 那位程序达人试一下啊，或者给我讲讲那些证明 一题 最多 3人 2题 最多 4人 3题 最多 6人 4题 最多 9人 5题 最多 10<=x <=13 下面是4题9人的一种方案 1 1 1 1 2 1 3 2 3 2 3 1 3 3 1 2 1 2 2 2 2 3 2 1 3 1 2 3 1 3 3 3 2 2 1 3

风云剑

仔细研究了下，总算把题目看懂了。 程序搜索可以做，但是也很困难，组合数增长的太快了。而且判断也越来越复杂，在所有卷子中任选3张答卷，都有一道题的选择互不相同，看起来简单，但用程序很费时，要是这一步能有快速方法就好了。 我写了一个简单程序，算4题的情况已经力不从心了。 还有，程序求出n个人的解后，还要验证n+1个人无解，运算量极大

风云剑

shshsh_0510，你算出4题9人共多少种方案？

风云剑

想了半天，还有很多可以优化的地方。首先是同构现象。 1 1 1 1 2 1 3 2 3 2 3 1 3 3 1 2 1 2 2 2 2 3 2 1 3 1 2 3 1 3 3 3 2 2 1 3 这个矩阵，任意行交换，任意列交换，都是同构。 还有数字1、2、3任意替换，也是同构。 剔除这些同构，规模应该会小很多。

数学星空

我觉得这个问题需要借助拉丁方来构造.... 尤其要注意6阶拉丁方不存在.....

shshsh_0510

shshsh_0510，你算出4题9人共多少种方案？ 风云剑 发表于 2009-7-6 14:53

我算了两种就没继续。穷举的话搜索空间还是蛮大的。不过4题 $3^36/(9!*4!*3!)=O(10^9)$还是可以的

我觉得这个问题需要借助拉丁方来构造.... 尤其要注意6阶拉丁方不存在.....

两句话都不同意

风云剑

6题，要构造个12人的解还真困难。我程序算了半天，也只到11人。