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. enter image description here

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.

  • $\begingroup$ 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$. $\endgroup$ – Arthur Nov 17 '17 at 16:37
  • $\begingroup$ For $1)$ you can just swap the $x$s and $y$s. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – ZFR Nov 17 '17 at 16:53
  • $\begingroup$ Am I right in the above comment? $\endgroup$ – ZFR Nov 17 '17 at 17:00
  • $\begingroup$ @RFZ You just need $\lt (m-1)n$ because the induction hypothesis applies to the case of $m-1$ $\endgroup$ – Mark Bennet Nov 17 '17 at 17:10
  • $\begingroup$ Relating question 1 is it correct to change variables, i.e. writing $x$ instead of $y$y and vice versa? $\endgroup$ – ZFR Nov 17 '17 at 17:13
  • 1
    $\begingroup$ @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). $\endgroup$ – Mark Bennet Nov 17 '17 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.