Question

（04年北京卷）(12分)

给定有限正数满足条件T: 每个数都不大于50且总和L=1275.现将这些数按下列要求进行分组,每组数之和不大于150且分组的步骤是:

首先,从这些数中选择这样一些数构成第一组,使得150与这组数之和的差r₁与所有可能的其他选择相比是最小的,r₁称为第一组余差;

然后,在去掉已选入第一组的数后,对余下的数按第一组的选择方式构成第二组,这时的余差r₂;如此继续构成第三组(余差为r₃)、第四组（余差为r₄）、…，直至第N组（余差为r_N）把这些数全部分完为止。

(Ⅰ) 判断r₁,r₂,…，r_N的大小关系，并指出除第N组外的每组至少含有几个数；

(Ⅱ) 当构成n(n>N)组后，指出余下的每个数与r_n的大小关系，并证明

  ；

（Ⅲ）对任何满足条件T的有限个正数，证明：N≤11。

Answer 1

解析: (Ⅰ) r₁≤r₂≤r_N. 除第N组外的每组至少含有个数.

(Ⅱ) 当第n组形成后,因为n<N,所以还有数没分完,这时余下的每个数必大于余差r_n. 余下数之和也大于第n组的余差r_n,即 ,

由此可得

因为所以

(Ⅲ)用反证法证明结论. 假设N>11,即第11组形成后,还有数没分完,由(Ⅰ)和(Ⅱ)可知,余下的每个数都大于第11组的余差r₁₁,且,

故  余下的每个数> r₁₁≥r₁₀>

因为第11组数中至少含有3个数,所以第11组数之和大于37.5×3=112.5.

此时第11组的余差r₁₁=150―第11组数之和<150―112.5=37.5,

这与(*)式中r₁₁>37.5矛盾,所以N≤11.(12分)