Codeforces 849C Proof/Puzzle 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.
 A: Strong induction seems like it should work...
By using the straightforward approach of accumulating the big string one character at a time, we can see that the triangular number $T(n-1) = n(n-1)/2$ is a feasible value for the cost $C(n)$ of assembling a $n$-length string.
So our base case is $C(1)=0$.
Our strong hypothesis is that, for $ n< k,$ $C(n) =  n(n-1)/2$
Then $C(k) = C(a) + C(b) + ab$ from the final merge step, where $a+b=k$
So by the hypothesis,
$\begin{align}
C(k) &= a(a-1)/2 + b(b-1)/2 + ab \\
 &= (a^2 -a + b^2-b+2ab)/2 \\
 &= ((a+b)^2 -a -b)/2 \\
 &= ((a+b)(a+b) -(a +b))/2 \\
 &= ((a+b)(a+b-1) )/2 \\
 &= k(k-1) /2 \\
\end{align}$
as required.
A: 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$.
A: 
Hint: use induction and $T_n = \frac{n(n-1)}{2}$
