组合趣题 - 辕门射虎 - 轩辕春秋文化论坛 20周年


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#1

发表于 2005-10-23 22:12 资料主页短消息只看该作者

一个考试有六道题, 这六题里任意抽出两题, 都严格大于2/5的学生把这两题目全部做对. 没有一个学生做对全部六题目. 求证至少有两个人, 正好做对五题.

更改部分加蓝.

[广告] 《精忠报国岳飞传完整版》火热发布


	凤凰涅槃

组别	士兵
级别	忠义校尉
功绩	3
帖子	279
编号	51517
注册	2005-10-21

#2

发表于 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

好像满足条件

[广告] 真诚支持说岳，携手共创辉煌


	俺是马甲

组别	士兵
级别	偏将军
好贴	1
功绩	9
帖子	368
编号	28860
注册	2004-12-26

#3

发表于 2005-10-24 12:03 资料短消息只看该作者

QUOTE:

原帖由凤凰涅槃于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的话,我是有比较容易的方法证明命题的

[广告] 《精忠报国岳飞传完整版》火热发布


	俺是马甲

组别	士兵
级别	偏将军
好贴	1
功绩	9
帖子	368
编号	28860
注册	2004-12-26

#4

发表于 2005-10-24 12:05 资料短消息只看该作者

呵呵,不好意思,我看错了
我把下面那一行看成每个人会的题目的组合了
等我再仔细瞧瞧

[广告] 《精忠报国岳飞传完整版》火热发布


	俺是马甲

组别	士兵
级别	偏将军
好贴	1
功绩	9
帖子	368
编号	28860
注册	2004-12-26

#5

发表于 2005-10-24 12:07 资料短消息只看该作者

可以直接验证你的反例是对的
汗了

[广告] 《精忠报国岳飞传完整版》火热发布


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#6

发表于 2005-10-24 17:19 资料主页短消息只看该作者

题目记错了... 是严格大于2/5.

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	俺是马甲

组别	士兵
级别	偏将军
好贴	1
功绩	9
帖子	368
编号	28860
注册	2004-12-26

#7

发表于 2005-10-24 17:33 资料短消息只看该作者

QUOTE:

原帖由天宫公主于2005-10-24, 17:19:13发表
题目记错了... 是严格大于2/5.

那这个真的是可以解决的
就确实差不多是用的抽屉原理

[广告] 《精忠报国岳飞传完整版》火热发布


	俺是马甲

组别	士兵
级别	偏将军
好贴	1
功绩	9
帖子	368
编号	28860
注册	2004-12-26

#8

发表于 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)

[广告] 《精忠报国岳飞传完整版》火热发布


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#9

发表于 2005-10-25 00:39 资料主页短消息只看该作者

不错不错... 给个提示: 我的解法是把 2 mod 5 的情况, 分成3的倍数和非3的倍数. 非3的倍数相对容易一些... 大家加油!

[广告] 《精忠报国岳飞传完整版》火热发布


	凤凰涅槃

组别	士兵
级别	忠义校尉
功绩	3
帖子	279
编号	51517
注册	2005-10-21

#10

发表于 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的加起来

[广告] 《精忠报国岳飞传完整版》火热发布