找回密码
 欢迎注册
查看: 69676|回复: 42

[讨论] 有多少人参加考试

[复制链接]
发表于 2009-6-28 08:17:42 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
精华
试卷上有6道选择题,每题有3个选项(单选题,且不允许不选),结果阅卷老师发现,在所有卷子中任选3张答卷,都有一道题的选择互不相同,请问最多有多少人参加了这次考试?

(互不相同是指的完全不相同,即正好包括1、2、3三种答案。)

转自天涯
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-1 11:33:49 | 显示全部楼层
感觉难度很大
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-1 16:07:12 | 显示全部楼层
2# 风云剑
是复杂呢。感觉应该是19吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-3 14:59:41 | 显示全部楼层
这个比我想象的还复杂,我想了两天也没想通,太浪费时间了,决定先放弃,等有时间再想。
说说目前结果吧。网上有好多答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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-6 13:51:30 | 显示全部楼层
仔细研究了下,总算把题目看懂了。
程序搜索可以做,但是也很困难,组合数增长的太快了。而且判断也越来越复杂,在所有卷子中任选3张答卷,都有一道题的选择互不相同,看起来简单,但用程序很费时,要是这一步能有快速方法就好了。
我写了一个简单程序,算4题的情况已经力不从心了。
还有,程序求出n个人的解后,还要验证n+1个人无解,运算量极大
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-6 14:53:26 | 显示全部楼层
shshsh_0510,你算出4题9人共多少种方案?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-6 16:15:51 | 显示全部楼层
想了半天,还有很多可以优化的地方。首先是同构现象。
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任意替换,也是同构。
剔除这些同构,规模应该会小很多。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-6 17:46:48 | 显示全部楼层
我觉得这个问题需要借助拉丁方来构造....
尤其要注意6阶拉丁方不存在.....
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-6 20:05:54 | 显示全部楼层
shshsh_0510,你算出4题9人共多少种方案?
风云剑 发表于 2009-7-6 14:53

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

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

两句话都不同意
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-7 11:06:23 | 显示全部楼层
6题,要构造个12人的解还真困难。我程序算了半天,也只到11人。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 04:00 , Processed in 0.045005 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表