# Problem 20 from Putnam and Beyond

I encountered into problem from book "Putnam and Beyond" which seemed to me quite interesting. However, After a long meditation I can not solve it.

Let $x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m$ be positive integers, $n,m>1$. Assume that $x_1+x_2+..+x_n=y_1+y_2+\dots+y_m<mn$. Prove that in the inequality $$x_1+x_2+..+x_n=y_1+y_2+\dots+y_m$$ one can suppress (but not all) terms in such a way that the equality is still satisfied. I read the solution which is attached above. However, I have couple of questions.

1) WLOG they assume that $x_1\geqslant y_1$. However, I dont know how to work with the inverse inequality $x_1\leqslant y_1$. Can anyone explain how to work with it?

2) They state that $y_1$ should be moved back to the right-hand side? What if $x_1-y_1$ is already suppressed by induction hypothesis?

3) Why in the case $y_1<n$ this argument does not work? I can not even understand what namely does work.

The solution, in general, is written in unclear way. Would be grateful for clear explaining.

• 1) If you have the reverse case, change the name of all the $x_i$ to $y_i$ and all the $y_i$ to $x_i$. Now it is true that $x_1\geq y_1$. If you don't like to change the name of the variables, you can keep them as they are, and just change every single mention of $x$ in the proof text into a $y$, and every $y$ into an $x$. – Arthur Nov 17 '17 at 16:37
• For $1)$ you can just swap the $x$s and $y$s. – Mark Bennet Nov 17 '17 at 16:37

For $2)$ if that term is already suppressed you don't need to do any more - you have a sum of $x$s $=$ a sum of $y$s.
For $3)$ if $y_1\lt n$ the remaining sum might be too large to apply the inductive hypothesis.
• Hmm yes. And they estimate the remaining sum $y_2+\dots+y_m\leqslant (m-1)y_1<(m-1)n<mn$ and apply the induction hypothesis. – ZFR Nov 17 '17 at 16:53
• @RFZ You just need $\lt (m-1)n$ because the induction hypothesis applies to the case of $m-1$ – Mark Bennet Nov 17 '17 at 17:10
• Relating question 1 is it correct to change variables, i.e. writing $x$ instead of $y$y and vice versa? – ZFR Nov 17 '17 at 17:13
• @RFZ Well that exchanges $m$ and $n$ as well, but there is no assumption on these. So you have two sets of numbers whose sum is equal, and you choose the one with biggest number in it for the $x$ set (and if they have the same largest number, you are done anyway). – Mark Bennet Nov 17 '17 at 17:19