5
$\begingroup$

We have $a_1,a_2,...,a_n$, and $b_1,b_2,...,b_m$, all positive integers, with $a_i < m+1$ for all i, and $ b_j < n+1$ for all j. It is known that $m>n$, and that the sum of $b_1,..,b_m$ is strictly larger than the sum of $a_1, a_2,...,a_n$. Show that there is a subset of $a_1,..,a_n$ whose sum is equal to the sum of a subset of $b_1,...,b_m$.

I know this should be solvable using the pigeonhole principle on several sequences, but I just can't seem to find the sequence that works. I tried using sequences that excluded one of the values, but I think that since there are so many possible sequences, this just won't work, and using all possible sums seems pretty hard to do, since there can be multiple occurrences of the same number.

I would greatly appreciate any hints, thanks!

$\endgroup$
4
  • $\begingroup$ "I know this should be solvable using the pigeonhole principle" Do you actually know this? $\endgroup$ Commented Dec 30, 2020 at 14:50
  • $\begingroup$ @mathworker21 It was from a sequence pigeonhole principle problem set, so that should be the case $\endgroup$ Commented Dec 30, 2020 at 14:54
  • 4
    $\begingroup$ You may want to give a look to this thread math.stackexchange.com/questions/496113/… $\endgroup$
    – Suzet
    Commented Dec 30, 2020 at 18:14
  • $\begingroup$ @Suzet Thanks! Should I just delete this question then? $\endgroup$ Commented Dec 31, 2020 at 9:31

1 Answer 1

3
+25
$\begingroup$

Arrange the numbers so that $a_1 \le a_2 \le \dotsb \le a_n$ and $ b_1 \le b_2 \le \dotsb \le b_m$, now consider the sums $P_k = a_1+ a_2+ ... + a_k$, $Q_l= b_1+b_2+ \dotsb b_l$, then call $t_k$ the number such that $Q_{t_k} \le P_k < Q_{t_k +1}$. Then, since $b_{t_k+1} \le n$, $P_k -Q_{t_k} < n$, and we have $n$ such differences, so by Pigeonhole theorem we have two equal differences.

WLOG, assume that $P_k -Q_{t_k} = P_m -Q_{t_m}$, then we have $P_k-P_m=Q_{t_k} - Q_{t_m}$ which means $ a_{m+1}+a_{m+2}+ \dotsb + a_k = b_{t_k +1} +b_{t_k +2} +\dotsb + b_{t_m}$.

Q.E.D $\square$

$\endgroup$
2
  • 1
    $\begingroup$ Consider $A=\{1,1,1,...,1,2\}$ and $B=\{n,...,n\}$ - and make sure to include $P_0$ & $Q_0$ :-) $\endgroup$
    – Joffan
    Commented Jan 6, 2021 at 1:01
  • $\begingroup$ I see, thank you. $\endgroup$ Commented Jan 6, 2021 at 5:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .