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。

Answer 2

是的，请给原题

Answer 3

请给原题，谢谢