# How to prove that answer is either $n-1$ or $n$?

Given a list of integers of length $$n$$. I can pick any two elements, let's denote them $$a_i$$, $$a_j$$. where $$i \neq j$$. and increase $$a_i$$ by $$1$$ and decrease $$a_j$$ by $$1$$. We can repeat this operation infinitely until we maximize our answer. The task is to make the maximum number of equal elements. I managed to observe that we can make either $$n - 1$$ equal elements or $$n$$ equal elements. But I don't know how to prove it.

Examples:

$$[1, 2, 3]$$. Increase $$a_1$$ and decrease $$a_3$$. then you make $$3$$ equal elements which are $$[2, 2, 2]$$. Answer is $$n$$ in this case.

Another example:

$$[1, 2, 3, 4]$$. Increase $$a_1$$ decrease $$a_4$$. list now is $$[2, 2, 3, 3]$$. Increase $$a_3$$ decease $$a_4$$. List is now $$[2, 2, 4, 2]$$. which is $$n - 1$$.

Any hints on how to prove that answer is either $$n$$ or $$n-1$$.

• Are we referring to a list of consecutive integers, or an arbitrary list of integers? And can we make only one choice of $a_i$ and $a_j$, or do we just repeat this process until we've maximized the number of equal elements? Aug 30, 2020 at 3:18
• @StephenGoree they're not necessarily consecutive, and yes we can repeat until the answer is maximized. Aug 30, 2020 at 3:24

Note increasing an element by $$1$$ and decreasing another element by $$1$$ means the overall sum of the elements doesn't change. To end up with all of the $$n$$ elements being the same means the sum must be a multiple of $$n$$, so you can't do this otherwise.

With your first example where $$n = 3$$ of $$[1, 2, 3]$$, the sum is $$6 = 3 \times 2$$. Thus, since it's a multiple of $$n = 3$$, you can get all of the elements to be the same. However, with your second example where $$n = 4$$ of $$[1, 2, 3, 4]$$, the sum is $$10 = 4 \times 2 + 2$$, i.e., it's not a multiple of $$n = 4$$. This is why you can get at most $$n - 1 = 3$$ elements to be the same.

Regarding confirming you can get the number of elements which are the same to be $$n$$ or $$n - 1$$, consider first for $$n$$. Let the sum of the elements be $$s = kn$$ for some integer $$k$$. If not all of the elements are already $$k$$, then there must be at least one below and one above (since if all the non-$$k$$ elements are $$\gt k$$ then the sum would be $$\gt kn$$ and, similarly, if they are all $$\lt k$$ then then sum would be $$\lt kn$$). Choose these $$2$$ elements and repeatedly increase the one below $$k$$ and decrease the one above $$k$$ until one or both of them are $$k$$, so there are now one or two more elements which are $$k$$. Repeat this process until all of the $$n$$ values are $$k$$.

If the sum is not a multiple of $$n$$, say it's $$s = kn + r$$ for some integer $$1 \le r \lt n$$, then if there is no element with a value of $$k + r$$, choose any $$2$$ elements and for one of them, say it's larger than $$k + r$$, repeatedly decrease it and increase the other element until the first element is $$k + r$$. Next, not including this $$k + r$$ element, the sum of the other $$n - 1$$ elements is $$s - (k + r) = kn + r - k - r = kn - k = k(n - 1)$$. Now use the procedure I outlined in the paragraph above to get these $$n - 1$$ elements to all be the same value of $$k$$.

You can take $$a_1$$ and $$a_2$$ and do the increase-decrease process, and make $$a_1$$ become $$x$$. Next, you can take $$a_2$$ and $$a_3$$ and do it again to make $$a_2$$ become $$x$$.

So on, so on, and so on. Eventually you will have:

$$a_1=a_2=a_3=……=a_{n-1}=x$$

What $$a_n$$ is doesn’t matter at this point.

Now:

If the sum of all the elements can be divided by $$n$$ (since the sum won’t change at all), you can do the process a couple times by taking $$a_n$$ and another element, eventually all the elements will be the same. Therefore you can make $$n$$ equal elements in this case.

If not, you can only make at most $$n-1$$ equal elements.