2010NOIP提高初赛问题求解第三题求证明!
来源:学生作业帮 编辑:百度作业网作业帮 分类:数学作业 时间:2024/08/17 19:05:30
2010NOIP提高初赛问题求解第三题求证明!
记T为一队列,初始时为空,现有n个总和不超过32的正整数依次入列.如果无论这些数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列T中的数之和恰好为9,那么n的最小值是___________.
记T为一队列,初始时为空,现有n个总和不超过32的正整数依次入列.如果无论这些数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列T中的数之和恰好为9,那么n的最小值是___________.
![2010NOIP提高初赛问题求解第三题求证明!](/uploads/image/z/9406073-65-3.jpg?t=2010NOIP%E6%8F%90%E9%AB%98%E5%88%9D%E8%B5%9B%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3%E7%AC%AC%E4%B8%89%E9%A2%98%E6%B1%82%E8%AF%81%E6%98%8E%21)
本题可用抽屉原理求解.
设 为各正整数值,则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.
设 为各正整数值,则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.