9.6. Twenty-five coins are arranged into piles as follows. First, they are arbitrarily divided into two groups. Then any of the existing groups is again divided into two groups, and so on until each group consists of one coin. Each time a group is divided into two, the product of the number of coins in the two resulting groups is recorded. What can the sum of all recorded numbers be?
Answer: 300.

Solution. First method. Let's represent the coins as points and connect each pair of points with a segment. We will get $\frac{25(25-1)}{2}$ $=300$ segments. With each division of one group of coins into two, we will erase all segments connecting points corresponding to coins that end up in different groups. Suppose at some step we divide the coins of one of the already existing groups into two groups of $x$ and $y$ coins. Then we erase $x y$ segments. This is the number we record. Thus, the sum of the recorded numbers is the total number of erased segments. Since there were initially 300 segments, and in the end, all segments are erased, the total number of erased segments is 300.

Second method. Consider the variable quantity $S$, equal at each moment to half the sum of the squares of the number of coins in the piles. Initially, $S=\frac{25^{2}}{2}=312.5$, and at the very end, $S=\frac{1^{2}+1^{2}+\ldots .+1^{2}}{2}=\frac{25}{2}=12.5$. If a pile with $x+y$ coins is divided into two piles of $x$ and $y$ coins, then $S$ decreases by $\frac{(x+y)^{2}}{2}-$ $-\frac{x^{2}+y^{2}}{2}=x y$. Thus, with each division, the quantity $S$ decreases by the next recorded number. Therefore, the sum of all recorded numbers is equal to the total decrease in the quantity $S$, which is 312.5 $-12.5=300$.

Third method. We will prove by induction that if there are initially $n$ coins, then the desired sum is $\frac{n(n-1)}{2}$.

Base of induction. For $n=2$, after the first step, we get two piles with one coin each and record the number $1 \cdot 1=1$. Since the equality $\frac{2(2-1)}{2}=1$ is true, the statement is true for $n=2$.

Induction step. Assume the statement is true for all $n<k$ and prove that it is also true for $n=k$. Suppose on the first step $k$ coins are divided into two groups of $x$ and $y$ coins ( $k=x+y$ ). For $x$ and $y$ coins, the statement is true by the induction hypothesis.

If in such a division $x \geqslant 2$ and $y \geqslant 2$, then the recorded sum is

$$
x y+\frac{x(x-1)}{2}+\frac{y(y-1)}{2}=\frac{x^{2}-x+y^{2}-y+2 x y}{2}=\frac{(x+y)^{2}-(x+y)}{2}=\frac{k^{2}-k}{2}=\frac{k(k-1)}{2}
$$

If, however, $x=1$ and $y \geqslant 2$, then $k=y+1$ and the recorded sum in this case is $1 \cdot y+\frac{y(y-1)}{2}=\frac{(y+1)^{2}-(y+1)}{2}=$ $=\frac{k(k-1)}{2}$. According to the principle of mathematical induction, the statement is proven for any natural $n \geqslant 2$. In particular, for 25 coins, we get: $\frac{25(25-1)}{2}=300$.

## Grading criteria:

+ a complete and well-reasoned solution is provided

$\pm$ the correct answer and a generally correct solution with minor inaccuracies or gaps is provided

- only the answer is provided