Problem 20 from Putnam and Beyond

Question

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.

For $1)$ you can just swap the $x$s and $y$s. – Mark Bennet Nov 17 '17 at 16:37 — Mark Bennet, Nov 17 '17 at 16:37

score 1 · Accepted Answer · answered Nov 17 '17 at 16:44

1

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.

answered Nov 17 '17 at 16:44

Mark Bennet

100,194

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. – RFZ Nov 17 '17 at 16:53
Am I right in the above comment? – RFZ Nov 17 '17 at 17:00
@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? – RFZ Nov 17 '17 at 17:13
1

@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
Maybe my words sound weird. We are going to understand the case $y_1\geqslant x_1$ but we are changing the variables and are working with above case. This transition seems quite unclear and difficult – RFZ Nov 17 '17 at 17:26
@RFZ It is just renaming the two sets, which we are entitled to do before we've done anything with them. – Mark Bennet Nov 17 '17 at 17:47
I will rethink on the problem. Anyway thanks a lot for clear answers to unclear questions :) – RFZ Nov 17 '17 at 18:00

Problem 20 from Putnam and Beyond

1 Answers1