2010NOIP提高初赛问题求解第三题求证明!记T为一队列,初始时为空,现有n个总和不超过32的正整数依次入列.如果无论这些数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列T中的数之

Question

2010NOIP提高初赛问题求解第三题求证明!
记T为一队列,初始时为空,现有n个总和不超过32的正整数依次入列.如果无论这些数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列T中的数之和恰好为9,那么n的最小值是___________.

Answer 1

本题可用抽屉原理求解.
设 为各正整数值,则T的队列顺序为 a1,a2,a3… an,设bi为前i项数之和,则 b0=0,b1=a1 ,b2=a1+a2 ,b3=a1+a2+a3 ….如队列T中的数之和恰好为9,实际上即是找到某个bj和bi ,使得 bj-bi=9.由题意可知bi取值范围为1-32,现将这32个数构造为集合{1,10}, {2,11}, …, {8,17}, {18,27}, {19,28},…,{23,32} ,{24},{25},{26},这17个集合中的任一个集合不能包含两个或两个以上的 ,否则它们的差为9.例如设n=17时,队列T为 11111111 10 11111111,即 b1=1, b2 =2,… b8=8, b9 =18, b10=19, b11=20… b17=26,它们中没有任意两个数是在同一集合内的,所以不存在数之和恰好等于9.
故根据抽屉原理可得,当n=18时,至少存在两个 在同一个集合,即它们的差为9.
因此,答案为n=18.