鳩の巣原理を使用して、同じ合計のシーケンスがあることを示す

Dec 28 2020

我々は持っています $a_1,a_2,...,a_n$、および $b_1,b_2,...,b_m$、すべて正の整数、 $a_i < m+1$ すべての私のために、そして $ b_j < n+1$すべてのjのために。と知られている$m>n$、およびその合計 $b_1,..,b_m$ の合計よりも厳密に大きい $a_1, a_2,...,a_n$。のサブセットがあることを示す$a_1,..,a_n$ その合計はのサブセットの合計に等しい $b_1,...,b_m$

これはいくつかのシーケンスで鳩の巣原理を使用して解決できるはずですが、機能するシーケンスを見つけることができないようです。値の1つを除外したシーケンスを使用してみましたが、可能なシーケンスが非常に多いため、これは機能せず、同じものが複数回出現する可能性があるため、すべての可能な合計を使用するのはかなり難しいようです。数。

ヒントをいただければ幸いです。ありがとうございます。

回答

2 NikolaTolzsek Dec 31 2020 at 21:18

次のように番号を配置します $a_1 \le a_2 \le \dotsb \le a_n$ そして $ b_1 \le b_2 \le \dotsb \le b_m$、今、合計を考慮してください $P_k = a_1+ a_2+ ... + a_k$$Q_l= b_1+b_2+ \dotsb b_l$、次に電話 $t_k$ そのような数 $Q_{t_k} \le P_k < Q_{t_k +1}$。その後、$b_{t_k+1} \le n$$P_k -Q_{t_k} < n$、そして私たちは $n$ そのような違いがあるので、鳩の巣定理によれば、2つの等しい違いがあります。

WLOG、 $P_k -Q_{t_k} = P_m -Q_{t_m}$、それから私たちは持っています $P_k-P_m=Q_{t_k} - Q_{t_m}$ つまり、 $ a_{m+1}+a_{m+2}+ \dotsb + a_k = b_{t_k +1} +b_{t_k +2} +\dotsb + b_{t_m}$

QED $\square$