6

Let $m$ and $n$ be positive integers. Positive integers $x_1,x_2,...,x_n,y_1,y_2,...,y_m$ satisfy the following conditions: $x_1+x_2+...+x_n=y_1+y_2+...+y_m<mn$.

Prove that it is possible to remove some terms from both sides (but not all terms) of the equality, so that the equality is still satisfied.

I have tried to write an inductive proof, but it seems to lead nowhere. Even considering some simpler cases, for example, fixing $n=2$, it is still not obvious why the problem statement is true.

On the other hand, the condition $<mn$ would maybe suggest that the solution should involve some clever use of the Pigeonhole principle, for example, if we consider the number of different sums we can get on both sides by removing terms. Again this also seems to fail.

For some context, even though this problem originates from a mathematical competition intended for high-school students, this problem was given, a while ago, as an exercise in my college Combinatorics class. Considering that, I am very skeptical of using some standard "olympiad" techniques, and just wondering if this could have any connection to partitions or some clever use of generating functions?

Link to AOPS thread (which is empty :( ): https://artofproblemsolving.com/community/u492589h1869901p27929397

RobPratt
  • 45,619
eulers_barber123
  • 63
  • 5

1 Answers1

2

The $<mn$ seems to suggest Pigeon hole as you say. Let’s explore. We want $mn$ sets. One possibility is to define $S_{i,j} = x_i + y_j$. Problem is they might exceed $mn$ so there would be $2mn -2$ holes. Hmm, that does’t seem to work. How can we squeeze that into at most $mn-1$ holes? Let’s take the answer mod $mn-1$.

That gives us at most $mn-1$ values so there must be $i,j,k,l$ such that $x_i + y_j = x_k + y_l \mod mn-1$. Rearranging, we get $x_i - x_k = y_l - y_j \mod mn-1$. Hmm, that’s not exactly what we need. This seems to tell us the difference between two elements is the same modulo $mn-1$.

Can we redefine the sets so that the above expression is a sum? The only fact we used above is that there are $mn$ summations. They don’t neccessarily need to be $x_i+y_j$! Aha, if they are contigious intervals, then maybe the subtraction works out for us!

Try 2: let $S_{i,j} = x_1 + … + x_i + y_1 + … + y_j$. There are still $mn$ sets and we take it mod $mn-1$, so there exists $i,j,k,l$ such that $x_1+…+x_i+ y_1+…+y_j = x_1+…+x_k + y_1+…+y_l \mod mn-1$. Almost there! If $i=k$ then we’re in trouble because a bunch of y variables sum to zero, which is impossible. So either $i<k$ or $i>k$. Assume WLOG that $i< k$. Then we get:

$$x_{i+1} + … + x_k = y_1 + … + y_j - y_1 - … - y_l \mod mn-1$$

If $j>l$, then we are done! Two sums that are equal, mod $mn-1$ and they are less than $mn-1$ so they are actually equal. But what about if $l > j$. Darn it, we are stuck.

Is there hope to save this? What else do we have? We changed the sets, and they seem to work except for this pesky set. What other freedom do we have? One “arbitrary” thing we did was take mod $mn-1$. Ok, let’s try setting it to $V<mn$ (to keep the holes number small). What can we do in modulo arithmetic? Well, we can add $V$ to any side. Let’s do that:

$$x_{i+1} + … + x_j = -y_{j+1} - … -y_l + V \mod V$$

Can we retrieve any sum from the RHS for any choice of V? What if $V$ is exactly the common sum? We get some $x$s and some $y$s sum to each other modulo the common sum! But since they are less than the common sum, then they are actually equal! We’re done.

AspiringMat
  • 2,483
  • 1
  • 17
  • 32