做了一天,有了一些思路,希望大家能补全证明。
当题目的个数为N时, 设总人数为S_N,定义第一题选A的所有卷子为A组、人数为S_NA, 选B的为B组、人数为S_NB,选C的为C组、人数S_NC。
首先,易知在N为任意值的情形下,不存在两份卷子答案完全一样,否则包含这两份卷子的任意三份卷子,都无法找到一题答案完全不同。
当 N = 1 时, 易知 S_1 为3
当 N = 2 时, 分三种情形讨论
1 抽选的三份卷子分别来自A、B、C三组,第一题3个答案自然形成 ABC, 符合题目约束。
2 抽选的三份卷子来自同一组内部(只对该组人数>=3的组,才存在此种情形), 由于第一题三份卷子答案完全一样,第二题必须满足任选三份答案不同 , 递归到N = 1的情形
S_2A <=3 (1)
S_2B <=3 (2)
S_2C <=3 (3)
3 抽选的三份卷子来自两组 (只对该两组人数>=3的两组,才存在此种情形),由于第一题三份卷子答案无法实现互不相同,第二题必须满足任选三份答案不同 , 递归到N = 1的情形
S_2A + S_2B <=3 (4)
S_2A + S_2C <=3 (5)
S_2B + S_2C <=3 (6)
显然, 满足(4),(5),(6)必然满足(1),(2),(3)
由 (4)+ (5) +(6) 推出, 2(S_2A + S_2B +S_2C)<=9 , 即 S_2 = S_2A + S_2B +S_2C <=4.5 , 取整 S_2 <=4
同理利用递归法, 推出 , S_3 <= S_2 *3/2 <= 6, S_4 <= S_3 * 3/2 = 9, S_5 <= S_4*3/2 = 13.5 取整13, S_6<=S_5 *3/2 = 19.5, 取整19
下面的问题就是证明, S_3=6, S_4=9, S_5 =13, S_6=19 是可以实现的
--
修改:nbg FROM 114.255.229.*
FROM 114.255.229.*