[组合] 选择题人数问题

渐近自由：
有31个人同时做10道选择题，且每人都至少做对6道题。求证：至少有2人做对同样的5道题.

(当作是四项单选题)

分享到: QQ空间 腾讯微博 腾讯朋友

caijinzhi

2^#

发表于 2015-7-13 17:41 | 只看该作者

图论？

TOP

tommywong

3^#

发表于 2015-7-13 20:37 | 只看该作者

10题做对6题且没有2人做对相同的5题
等价于10题做错4题且2人至少做错不同的2题

考虑第1,2,3,4题有没有做错
{1,2,3,4}（有四题做错）,{1,2,3,X}-{4}（有三题做错）,{1,2,X,X}-{3,4},{1,X,X,X}-{2,3,4},{X,X,X,X}-{1,2,3,4}
可设第一人就把第1,2,3,4题做错，第二个人一定不能再做错当中三题，有三题做错的情况不需要考虑

{1,2,3,4}

{1,2,5,6},{1,2,7,8},{1,2,9,10}
{1,3,5,7},{1,3,6,9},{1,3,8,10}
{1,4,5,8},{1,4,6,7}
{3,4,5,6},{3,4,7,8},{3,4,9,10}
{2,4,5,7},{2,4,6,9},{2,4,8,10}
{2,3,5,8},{2,3,6,7}

{1,5,9,10},{1,6,8,10},{2,7,9,10}

{5,6,7,8}

1+16+3+1=21组
实际上我弄不出30组

很难证明21就是上界，也不知道是不是。
以下我再缩小范围穷举，但还是不具理论性的。
考虑没有其他情况限制时第1,2,3,4题有两题做错的情况，最多能有16组
第1,2,3,4题有一题做错时
{1,5,6,7},{1,5,8,9},{1,6,8,10}
{2,5,6,8},{2,5,7,9},{2,6,7,10}
{3,5,6,9},{3,5,7,10},{3,6,7,8}
{4,5,6,10},{4,5,7,8},{4,6,7,9}
最多能有12组
第1,2,3,4题都没有做错时
{5,6,7,8},{5,6,9,10},{7,8,9,10}
最多能有3组
共1+16+12+3=32组

而实际上第1,2,3,4题都没有做错的情况跟有一题做错的情况有很大冲突
没有那3组的话共1+16+12=29组

设a(n,m)表示n题做错m题且2人至少做错不同的2题
按题设求a(10,4)的上界
$a(n,2)=[\dfrac{n}{2}],a(n,m)=a(n,n-m)$
根据刚才对第1,2,3,4题的分析有：
$a(n,m)\le 1+6a(n-4,m-2)+4a(n-4,m-1)+a(n-4,m)$
$a(10,4)\le 1+6a(6,2)+4a(6,3)+a(6,4)=22+4a(6,3)$
遗憾的是就算知道$a(6,3)=4$也达不到题目要求

TOP

其妙

4^#

发表于 2015-7-25 10:30 | 只看该作者

回复 3# tommywong

，

TOP

realnumber

5^#

发表于 2015-7-25 11:05 | 只看该作者

本帖最后由 realnumber 于 2015-7-25 11:07 编辑

模仿2楼的转换办法
2人做10题，每人做对其中6题，即为每人做错4题.2人做对相同的x+2题，即为做错相同的x题，x=0,1,2,3,4.
p(n)含义如下：表示n人做10题且每人做对6题的条件下，存在2人至少有p(n)题错得一样.
显然p(2)=0,p(3)=p(4)=p(5)=1,p(5)=1构造如下，题目编号依次为0,1,2,3,4,5,6,7,8,9,
那么5人做错的题目编号依次为(2,3,8,9),(1,3,4,5),(1,2,6,7),(0,5,7,9),(0,4,6,8).
下面证明p(6)=2.
假设p(6)=1
6人一共做错$6\times 4=24$题次，至少有1题被3人同时做错(若有2题被2人以上做错，与假设矛盾)
即3人除一题相同外，其余3题各不相同，即10题都在了，考虑任意另外一人，按抽屉原理，从3个抽屉里选，至少有一个抽屉被选中2次，即这个人与被选中的那人，已经做错相同2题，与假设矛盾。
经构造易得p(6)=p(7)=.....=p(15)=2,暂不知道p(16)以及以后.
1楼就是要证明p(31)=3

TOP

realnumber

6^#

发表于 2015-7-31 14:33 | 只看该作者

本帖最后由 realnumber 于 2015-8-6 11:19 编辑

1楼问题的证明：
只需要证明每人恰好做对6题的情景.也即每人恰好做错4题.
要证明存在2人做对同样的5题，即要证明存在2人做错同样的3题.
又$C_{10}^3=120<31\times C_4^3=124$,
由抽屉原理,可见存在2人做错同样的3题，
1楼得证.

假设30人可以出现这样情景：没有2人做错同样的3题，
那么不同的3题搭配有$30\times C_4^3=120=C_{10}^3$,即每种不同的3题都必须出现，都出现1次，意味着每题都错一样多次数，每2题的组合也一样.
$\frac{30C_4^2}{C_{10}^2}=4$,即每2题的组合都出现4次.
（比如某2题的一个组合01只能有4个搭配如下.0123,0145,0167,0189（一个搭配0123意思指某个人做错编号为0，1，2，3四题）.注意到此时每个编号都出现了，这4个除0,1，其余编号都出现且必须出现一次.）
因为每2题的组合出现一样多，且都出现，不妨如下构造
A={0,1},B={2,3,},C={4,5},D={6,7},E={8,9}这5个集合任意取2个搭配有$C_5^2=10$.
其余取法只能5个集合选4个，每个集合挑一个元素（若选2个元素,则与刚才选出的10种中某一个，有相同的3题）
5个集合选4个集合有$C_5^4=5$种,因此每选定4个集合，
各抽一个编号，必须要凑齐4个搭配，这样才有$5\times4+10=30$人.

{0,1},{2,3,},{4,5},{6,7},{8,9}这5个集合任意取2个搭配有$C_5^2=10$.
又0249,0256,0278,0347,0358,0369,0579,0648
1246,1258,1279,1349,1357,1368,1478，1569
共26人.
这样说明p(6)=p(7)=...=p(26)=2,

TOP

返回列表回复发帖

[组合] 选择题人数问题

[收藏此主题] [关注此主题的新回复]

[通过 QQ、MSN 分享给朋友]