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

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

but not

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

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

Almost forgot: The minimum is, of course,

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

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.

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.