标题: 组合趣题 [打印本页]
作者:
天宫公主 时间: 2005-10-23 22:12
一个考试有六道题, 这六题里任意抽出两题, 都严格大于2/5的学生把这两题目全部做对. 没有一个学生做对全部六题目. 求证至少有两个人, 正好做对五题.
更改部分加蓝.
作者:
凤凰涅槃 时间: 2005-10-24 11:56
我觉得应该不包括2/5吧，假设有5个同学A,B,C,D,E，6个题1,2,3,4,5,6，则：
A:12345 B:2346 C:1236 D:2356 E:1456
对应
1:ACE 2:ABCD 3:ABCD 4:ABE 5:ADE 6:BCDE
好像满足条件
作者:
俺是马甲 时间: 2005-10-24 12:03
原帖由凤凰涅槃于2005-10-24, 11:56:13发表
我觉得应该不包括2/5吧，假设有5个同学A,B,C,D,E，6个题1,2,3,4,5,6，则：
A:12345 B:2346 C:1236 D:2356 E:1456
对应
1:ACE 2:ABCD 3:ABCD 4:ABE 5:ADE 6:BCDE
好像满足条件
呵呵,我今天早上也发现她的这个题目不对了
不过,你这个反例肯定是不对的
只有每个人都会四题才有可能出现反例哦
不过,事实上构造的反例是15个人的
我假设每个人都会四个题目,
而且15个人恰好对应从6个题目中取四个的15个组合
然后很容易验证恰好满足题意,成为反例
但是,如果人数是模5余1,2,3,4的话,我是有比较容易的方法证明命题的
作者:
俺是马甲 时间: 2005-10-24 12:05
呵呵,不好意思,我看错了
我把下面那一行看成每个人会的题目的组合了
等我再仔细瞧瞧
作者:
俺是马甲 时间: 2005-10-24 12:07
可以直接验证你的反例是对的
汗了
作者:
天宫公主 时间: 2005-10-24 17:19
题目记错了... 是严格大于2/5.
作者:
俺是马甲 时间: 2005-10-24 17:33
原帖由天宫公主于2005-10-24, 17:19:13发表
题目记错了... 是严格大于2/5.
那这个真的是可以解决的
就确实差不多是用的抽屉原理
作者:
俺是马甲 时间: 2005-10-24 20:22
刚刚仔细算了一下
对于人物模5不作2的情况,偶还是能解决的
至于模5余2的情形,本人不打算伤脑筋了:
设人数为N=5k+i,i=0,1,2,3,4
我的思路是算一个计数:其法则是如果某人会指定的某两道题
则我的这个计数加1,那么:
从6个题目的两两组合来说,有15种组合
对于每种组合,至少有2k+1(i=0,1,2)或者2k+2(i=3,4)个计数点
故而总有:30k+15(i=0,1,2)或者30K+30(i=3,4)个计数点
从N个人来说,如果设有x人会五道题,则总的计数不大于:
10x+6*(N-x)=30k+4x+6i
则综合上面两点,应该有:4x+6i>=15(i=0,1,2)或者4x+6i>=30(i=3,4)
由此可以解得:x>=2(i不为2)
作者:
天宫公主 时间: 2005-10-25 00:39
不错不错... 给个提示: 我的解法是把 2 mod 5 的情况, 分成3的倍数和非3的倍数. 非3的倍数相对容易一些... 大家加油!
作者:
凤凰涅槃 时间: 2005-10-25 22:22
其实只用考虑一种情况就行了，就是第一个人修5门课，其他人都修4门课
我来解余数为2的情况，假设和马甲兄的一样：
则总计数冗余量为1，前两人只有两种情况：
i. A:12345 B:1236 ...... 冗余的计数为(16)
ii. A:12345 B:1234 ...... 冗余的计数为(12)
考虑其中一种情况：可以计算出剩下的5k个人中各个计数的个数m_(i,j)，进而算出在5k个人中每门课的选择次数n_(i)=sum_(i)(m_i,j)/3，结果必须都是整数，否则会增加新的冗余计数。实际上经验证两种情况都不满足。
注：sum_(i)(m_i,j)代表把所有下标为i的加起来
| 欢迎光临 轩辕春秋文化论坛 (http://www.xycq.org.cn/forum/) |
Powered by Discuz! 5.0.0 |