pigeonhole 원리를 사용하여 합계가 동일한 시퀀스가 있음을 보여줍니다.
우리는 $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$.
나는 이것이 여러 시퀀스에서 pigeonhole 원리를 사용하여 해결할 수 있어야한다는 것을 알고 있지만 작동하는 시퀀스를 찾을 수없는 것 같습니다. 값 중 하나를 제외한 시퀀스를 사용해 보았지만 가능한 시퀀스가 너무 많기 때문에 작동하지 않을 것이며 동일한 항목이 여러 번 발생할 수 있으므로 가능한 모든 합계를 사용하는 것이 매우 어려운 것 같습니다. 번호.
어떤 힌트라도 대단히 감사하겠습니다, 감사합니다!
답변
숫자를 정렬하여 $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$ 이러한 차이, 그래서 Pigeonhole 정리에 의해 우리는 두 개의 동일한 차이가 있습니다.
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$