给定有限个正数满足条件 $T$:每个数都不大于 $50$ 且总和 $L=1275$.现将这些数按下列要求进行分组,每组数之和不大于 $150$ 且分组的步骤是:
首先,从这些数中选择这样一些数构成第一组,使得 $150$ 与这组数之和的差 $r_{i}$ 与所有可能的其他选择相比是最小的,$r_{1}$ 称为第一组余差;
然后,在去掉已选入第一组的数后,对余下的数按第一组的选择方式构成第二组,这时的余差为 $r_{2}$;如此继续构成第三组(余差为 $r_{3}$),第四组(余差为 $r_{4}$),$\cdots\cdots$,直至第 $N$ 组(余差为 $r_{N}$).把这些数全部分完为止.
【难度】
【出处】
【标注】
  • 数学竞赛
    >
    简单组合
    >
    简单组合
  • 方法
    >
    思考方式
    >
    信息迁移
  • 数学竞赛
    >
    简单组合
    >
    简单组合
  • 方法
    >
    思考方式
    >
    信息迁移
  • 数学竞赛
    >
    简单组合
    >
    简单组合
  • 题型
    >
    组合数学
    >
    组合极值
  1. 判断 $r_{1},r_{2}\cdots,r_{N}$ 的大小关系,并指出除第 $N$ 组外的每组至少含有几个数;
    标注
    • 数学竞赛
      >
      简单组合
      >
      简单组合
    • 方法
      >
      思考方式
      >
      信息迁移
    答案
    $r_{1}\leqslant r_{2}\leqslant \cdots\leqslant r_{N}$,$3$
    解析
    由题意得,$$r_{1}\leqslant r_{2}\leqslant \cdots\leqslant r_{N}.$$除第 $N$ 组外的每组至少含有 $\dfrac{150}{50}=3$ 个数.
  2. 当构成第 $n(n>N)$ 组后,指出余下的每个数与 $r_{n}$ 的大小关系,并证明:$r_{n-1}>\dfrac{150n-L}{n-1}$;
    标注
    • 数学竞赛
      >
      简单组合
      >
      简单组合
    • 方法
      >
      思考方式
      >
      信息迁移
    答案
    余下的每个数必大于余差 $r_{n}$,证明略
    解析
    当第 $n$ 组形成后,因为 $n<N$,所以还有数没分完,这时余下的每个数必大于余差 $r_{n}$,余下数之和也大于第 $n$ 组的余差 $r_{n}$,即\[L-\left[(150-r_{1})+(150-r_{2})+\cdots+(150-r_{n})\right]>r_{n}.\]由此可得\[r_{1}+r_{2}+\cdots+r_{n-1}>150n-L.\]所以\[(n-1)r_{n-1}\geqslant r_{1}+r_{2}+\cdots+r_{n-1},\]所以$$r_{n-1}>\dfrac{150n-L}{n-1}.$$
  3. 对任何满足条件 $T$ 的有限个正数,证明:$N\leqslant 11$.
    标注
    • 数学竞赛
      >
      简单组合
      >
      简单组合
    • 题型
      >
      组合数学
      >
      组合极值
    答案
    解析
    用反证法.
    假设 $N>11$,即第 $11$ 组形成后,还有数没分完,由 $(1)$ 和 $(2)$ 可知,余下的每个数都大于第 $11$ 组的余差 $r_{11}$ 且 $r_{11}\geqslant r_{10}$.故余下的每个数均大于$$r_{11}\geqslant r_{10}>\dfrac{150\times 11-1275}{10}=37.5.$$因为第 $11$ 组数中至少含有 $3$ 个数,所以第 $11$ 组数之和大于 $37.5\times 3=112.5$.此时第 $11$ 组的余差 $r_{11}<150-112.537.5<37.5$,矛盾.因此 $N\leqslant 11$.
题目 问题1 答案1 解析1 备注1 问题2 答案2 解析2 备注2 问题3 答案3 解析3 备注3
0.253645s