2
$\begingroup$

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$.

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$ Aug 30, 2020 at 3:18
  • $\begingroup$ @StephenGoree they're not necessarily consecutive, and yes we can repeat until the answer is maximized. $\endgroup$ Aug 30, 2020 at 3:24

2 Answers 2

3
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .