免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 某群看到的一个关于抽屉原理问题


31位同学参加一次测试,有10题,每人至少做对6题,求证:存在2人,至少有同样5题做对了.
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

本帖最后由 realnumber 于 2017-7-22 06:07 编辑

未解决,只是有进展
引入符号f(x,y,z),x表示测试共x题,x-y表示做对题目数,y就是做错题目数,z表示任意两人最多有z题错得一样,f(x,y,z)表示最多可以有的人数.
例如f(4,2,1)具体每人答题可以如下,0,表示对,1表示错
1100
0110
0011
1001
1010
0101   这样说明f(4,2,1)≥6
又每一列,比如第一题错的情况下,最多有3人,一共有错误3×4=12
12÷2(每人错2题)=6,所以f(4,2,1)=6
以下是f(9,3,1)
000111000
111000000
000000111
100100100
010010010
001001001
100010001(123)
100001010(132)
010100001(213)
010001100 (231)..(321)..(312)                 
这样f(9,3,1)≥12,
又每一列错最多4人,一共有错误4×9=36,36÷3=12,f(9,3,1)≤12
即f(9,3,1)=12
接下来看f(8,4,2)
00001111
11110000
00110011
00111100
11001100
11000011
01100110
01101001
10010110
10011001
10101010
10100101
01011010
01010101
这样说明f(8,4,2)≥14,同样有$f(8,4,2)\le \frac{C_8^2\times 3\times 4}{C_4^2\times4}=14$,因此f(8,4,2)=14
而1楼问题$f(10,4,2)\le \frac{C_{10}^2\times 4\times 4}{C_4^2\times4}=30$
也就是说31位同学就符合存在2人,至少做对同样的5题。
但具体排除来还要少,已经有f(10,4,2)≥18,这里不排出来了,等解决了再发,
可以证明f(10,4,2)<30,但是否是18,还是没解决

已经有27≤f(10,4,2)<30,24是用程序搜索了部分(等了快1小时,才开始有解),27个的预设了5个初始值用一夜,
一个27的解如下:
1111000000
0011110000
0000111100
0000001111
1100000011
1010101000 1100110000 0000110011 0110001100 0001010110 0001101001 0010011001
0010100110 0011000101 0011001010 0100010101 0100101010 0101011000 0101100100  
0110010010 0110100001 1000011010 1000100101 1001001100 1001010001 1001100010
1010010100  

zsj-22xunhuan.pas (9.87 KB) zsj-10ticeshi.pas (528 Bytes)

TOP

本帖最后由 realnumber 于 2017-7-20 22:23 编辑

f(6,4,2)并不等于5
\[f(7,4,2)\le \frac{2C_7^2}{C_4^2}=7\]
1111000
1100110
0110011
1010101
1001011
0101101
0011110
所以f(7,4,2)=7,又以上看作7×7的矩阵,交换任意两行或两列,仍为f(7,4,2)问题的一组解,此性质于一般的f(m,n,p)问题也成立。
\[f(9,4,2)\le \frac{3C_9^2}{C_4^2}=18\]
用程序找到的众多解中的一个,为减低计算量,特意利用刚才的性质,把以下前2个,直接选入一组解中
111100000
000011110
000100111 001001011 001101100 001110001 010010101 010101001 010110010 011000110
011011000 100011001 100101010 100110100 101000101 101010010 110000011 110001100
zsj-f942.pas (497 Bytes) zsj-f942xunhuan.pas (5.6 KB)
因此f(9,4,2)=18

TOP

回复 1# realnumber

假设不然,则对任意2人,至多重复做对4题。
对于总数为6的题目,因为每人至少做对6题,因此只能有1人存在,如果存在2人,他们必定各自都做对全部6题,因此重复做对6题,与假设重复做对至多4题矛盾。称这种情况为6题能容纳1人。
显然7题也只能容纳1人,8题能容纳3人,只要证明9题也只能容纳3人,则因为10选9有10种选法,共能容纳30人,而有31人存在,导出矛盾。

假设9题能容纳4人$A,B_i,i=1,2,3$,为了能让容纳尽量多,只要让所有人都做对相同的4题。$A$与$B_i$组成3组。对每个$i$,$A,B_i$这组中的$A$至多与$B_i$重复做对4题,因此$A$必定与$B_i$至少做对不同2题,如果这三组的不同2题全不重复,则$A$与所有$B_i$做对的不同题目至少是6,而$A$与$B_i$做对的相同题目至少是4,共6+4>9矛盾,因此这三组的不同2题必有至少1题重复,但这样就存在两人做对相同5题的情况,也矛盾,因此9题不能容纳4人,于是9题至多容纳3人。

TOP

返回列表 回复 发帖