There is a pile with $15$ coins on a table. At each step, Pedro choses one of the piles in the table with $a>1$ coins and divides it in two piles with $b\geq1$ and $c\geq1$ coins and writes in the board the product $abc$. He continues until there are $15$ piles with $1$ coin each. Determine all possible values that the final sum of the numbers in the board can have.
Problem
Source: Cono Sur Math Olympiad 2020 #5
Tags: Products, Operation, Invariants, cono sur
27.12.2020 17:00
Induct on $n=15$ to prove that the answer is $n^3-n/3$.
30.04.2021 10:03
Very easy problem. The answer is $\frac{n^3 - n}{3}$ for all $n$. To prove this, I'll use induction. Suppose that its true until $k = n-1$ and we need to prove it for $n$ Suppose that the pile with $n$ coins has been divided into two piles with $a$ and $n-a$ coins. Then, the number added to the board is $an(n-a)$ and by the inductive hypothesis, the piles of $a, n-a$ coins will give a sum of $\frac{a^3 - a}{3}, \frac{(n-a)^3-(n-a)}{3}$ So, the total sum is $an(n-a) + \frac{a^3 - a}{3} + \frac{(n-a)^3-(n-a)}{3}$ $= \frac{3a^2n + 3an^2 + a^3 - a + n^3 - a^3 + 3a^2n - 3an^2 - n + a}{3}$ $= \frac{n^3 - n}{3}$ as desired
12.09.2021 17:01
I did it bounding things on $n=15$ and it took me 50 minutes. Hope this is right. Note that the first product and a pile with $b_1$ and $c_1$ coins is equal to $15.b_1.(15-b_1)$. Then, the idea is to maximize this product: case check with the values of $b_1$ gives that $b_1=\{ 9,6 \}$ works. But notice that $b_1=9$ or $b_1=6$ doesn't change anything, because $c_1$ would equal $6,9$ respectively and it gives the same result. Then, I did the same thing with $9$ and $6$, bounding things and writing the maximum value of the possible results, and the final answer becomes $1120$. Thus, let's bound things down, just to get a feeling of the answer: note that $b_1,c_1=\{ 1,14 \}$ minimize things, and then $b_2,c_2=\{ 1,13 \}$ minimizes things too. Hence, the sum $15x14+14x13+13x12+...+3x2+2x1$ gives the minimum value. But this sum equals $1120$, and (surprisingly) we are done. P.S: The key idea was to notice the invariant when you minimize and maximize things - if the pair $(b_i,c_i)$ on the $i-$ step gives the maximum/minimum value, then $(c_i,b_i)$ also does. $\blacksquare$