Question: I was working on a programming contest problem and I encountered the following sub-problem. The statement of the sub-problem is as follows:

* We are given a set of n of the same letter. For example, `n=3` would mean `set = {"a", "a", "a"}`.
* Our objective is to reduce the set to one element. We can pick any two elements `s` and `t` from the set and concatenate them. For example, we can select `s="a"` and `t="a"`, and the resulting set is `{"aa", "a"}`. Finally, we pick `aa` and `a` to achieve `{"aaa"}`.
* The cost of merging elements `s` and `t` is the product of their lengths. For example, the cost of merging `aa` and `a` is 2 x 1 = 2; the cost of merging `aa` and `aa` is 2 x 2 = 4.
* Prove that no matter what order you merge the elements of the set, the cost of reducing the set to one element will always be the same.

My work thus far: I considered a strategy where we always add each element of the set to a selected element. For example for `n = 4`, we would select `a` and `a`, then `aa` and `a`, and then `aaa` and `a`. I am able to show and prove that the total cost of this strategy is `f(n) = n * (n - 1) /2` since we are adding `1 + 2 + ... + n - 1`.

However, I'm struggling to prove that *any* other approach would also yield the same cost. I would very much appreciate a hint in the right direction to prove this.

Answer: 
Here's another, non-inductive argument for why the total cost is always the same.

If there is a cost of $ab$ to join a string $S$ of length $a$ and a string $T$ of length $b$, then that is the same as saying that we pay a cost of $1$ for each character of $S$ and each character of $T$ whenever they become part of the same string. (There are $ab$ ways to choose a pair of characters, one from $S$ and one from $T$, so these costs of $1$ add up to a cost of $ab$.)

We start with $\binom n2$ pairs of characters, all in different strings. At the end, all $\binom n2$ pairs are in the same string. So for each of these pairs, we've had to pay a cost of $1$ at some point: no matter when we did it, our total cost is $\binom n2$.
[![enter image description here](https://i.stack.imgur.com/4oVYa.png)](https://i.stack.imgur.com/4oVYa.png)

Hint: use induction and $T\_n = \frac{n(n-1)}{2}$