Can you minimise the arithmetic average?

Question

Let $n$ be a positive integer. There are $2n$ $1$s written on the whiteboard. John repeats the following procedure $3n$ times, as follows:

Choose two numbers $x,y$ on the board, then replace each of them by $2x+y, 2y+x$ respectively.

His goal is to make the arithmetic average of the numbers as low as possible. What is his best strategy and what is the best arithmetic average?

---

Problem in class work of Math Olympiad training, with some modifications.

---

Hint:

Use a commonly used inequality in IMO problems.

Answer 1

Note that this is not as obvious as it may appear at first sight. For example, the lazy assumption

the smaller the better

is not correct. Example $n=2$. Already after the first step which leads to $1,1,3,3$ the optimal next step is

$1,1$ or $3,3$

but not

$1,3$ even though it is smaller than $3,3$.

Before going into the technicalities of the actual proof let me first state what the trick is:

The trick is in the tracking: Don't think $x\mapsto 2x+y$, do think $x\mapsto x+2y$!

Formal proof (thanks @bobble for fixing my 'orrbile formatting):

Notation: it will be convenient to keep the same set of labels $\alpha,\beta,\gamma,...$ on the evolving numbers, so very formaly we have a state $X(k) = X_\alpha(k),X_\beta(k),...$ where $k$ is the step count. We will drastically abbreviate this by writing $a = X_\alpha(k),b = X_\beta(k)$ etc. As the labels have no influence on the mean we have a choice at each step , viz. $S^\times_{\alpha\beta}:a,b \mapsto a+2b,b+2a$ vs. $S^=_{\alpha\beta}:a,b \mapsto 2a+b,2b+a$. (We will stick with the first option and not use the second at all.) Of course, numbers not referenced are understood to remain unchanged. We will also need to be able to swap without actually processing: $\times_{\alpha\beta}: a,b \mapsto b,a$. Since this is purely book keeping it is understood that this kind of step does not count towards $k$.

We claim that the greedy strat, "always take the two smallest numbers" is optimal. This is obvious in the last step. Assume greedy has been shown to be optimal for the last $k$ steps regardless of state but there exists a state $X(3n-(k+1))$ at which taking the smallest two is not optimal. Let the optimal step be $S^\times_{\alpha\beta}$. By assumtion the optimal next step can be chosen to be the greedy one $S^\times_{\gamma\delta}$. Three cases:

1) $\alpha=\gamma,\beta=\delta$: Can't be because we assumed the first step to be non greedy.

2) $\alpha\ne\gamma,\beta\ne\gamma,\alpha\ne\delta,\beta\ne\delta$ Can't be because obviously

$S^\times_{\alpha\beta} \circ S^\times_{\gamma\delta}=S^\times_{\gamma\delta} \circ S^\times_{\alpha\beta}$ and we assumed greedy not to be optimal in the first step.

Before we settle the last case let us introduce the partial order $X(k)<X'(k)$ where $<$ means $X_\psi(k)\le X'_\psi(k)$ for all $\psi \in \{\alpha,\beta,...\}$ and at least one of the inequalities is strict. Obviously, if $X(k)<X'(k)$ and both are subjected to the same step then $X(k+1)<X'(k+1)$.

3) $\alpha\ne\gamma,\beta=\delta$ Then by assumtion $c<a$. Directly computing $X(3n-(k-1))$ yields

$S^\times_{\beta\gamma} \circ S^\times_{\alpha\beta}: a,b,c \mapsto a+2b,b+2a+2c,4a+2b+c$

if we use the original two steps which were assumed to be optimal.

If we swap them and afterwards also swap the labels $\alpha$ and $\gamma$ we get

$\times_{\alpha\gamma}\circ S^\times_{\alpha\beta} \circ S^\times_{\beta\gamma}: a,b,c \mapsto c+2b,b+2a+2c,4c+2b+a$

Because this state is componentwise better or equal to the one obtained by the supposedly optimal procedure this is a contradiction. $\square$

Almost forgot: The minimum is, of course,

27

Answer 2

Disclaimer: this is a cheeky answer.

Since the function is strictly increasing for all positive integers, the straightforward answer is to feed the function the smallest numbers at each stage. This results in $n$ applications taking (1,1) to (3,3), another $n$ operations taking (3,3) to (9,9), and the last $n$ operations taking (9,9) to (27,27), with an average of 27.

However, the Puzzling answer is that we should pick the definition of average more carefully. Instead of choosing the mean, we should pick the mode (the median works just as well in this case). Then, other than for $n=2$ (for which we'd use the 'straightforward' algorithm above), apply the function $3n$ times to the same pair of numbers. These numbers grow to $3^{3n}$, but all the rest remain 1.

The average for $n=1$ and $n=2$ is still 27, but for $n>2$, the average (median or mode) is now just 1.

Can we sweep the 2 anomalies under the rug? Well, yes, if we push the Puzzling angle further. Here's the problem statement:

His goal is to make the average of the numbers as low as possible. What is his best strategy and what is the best average?

It's not stated which "numbers" they're referring to, so let's pick the sequence of medians (media?) as the numbers: 27, 27, 1, 1, 1, ... . The median or mode of this infinite sequence is, of course, 1.

So the best average is 1, using the cheeky strategy (or 27, using the straightforward strategy).

Answer 3

Each step increases sum by the 2*(x+y). It is obvious that the minimum increase of sum in a particular step is if you take the lowest two numbers available. But this is not quite enough to show greedy algo is the best.

Take y=x+d and rewrite numbers after transformation to to 3x+d, 3x+2d. Now introduce another number w, w=x+e; e<d (and e >= 0). Another operation later, you end up with 3x+2d, 5x+2e+d, 7x+e+2d. Contrast those numbers with 3x+2e, 5x+e+2d, 7x+2e+d - first mixing x and w, then adding y to the mix. Differences are 2*(d-e); -(d-e); (d-e); and the sum clearly favors greedy algorithm. Even if you assume d is huge so the 2nd term would actually be the smallest in non-greedy case, differences are still 2x+d, -(2x+e), d-e - so while the 2nd term is again smaller in non-greedy case, sum of smallest 2 terms once again favors greedy algorithm.

I can't find an operation that would have ALL numbers smaller by greedy than non-greedy algorithm in every case, but the above shows that the sum of smallest 2 already favors greedy algorithm and I consider this good enough.