Numbers $1,2,\ldots,50$ are written on the board. Anya does the following operation: removes the numbers $a$ and $b$ from the board and writes their sum - $a+b$, after which also notes down the number $ab(a+b)$. After $49$ of this operations only one number was left on the board. Anya summed up all the $49$ numbers in her notes and got $S$. a) Prove that $S$ does not depend on the order of Anya's actions. b) Calculate $S$.
Problem
Source: Belarusian National Olympiad 2022
Tags:
RagvaloD
01.01.2025 21:00
a) Let $s_n=a_1+...+a_n, p_n=a_1a_2+...+a_{n-1}a_n,q_n=a_1a_2a_3+...+a_{n-2}a_{n-1}a_n$ Let prove by induction, that if numbers $a_1,a_2,...,a_n$ are on the board, then final $S_n$ is $s_np_n-q_n$ For $n=2$ it is true For $n=3$: $a_1,a_2,a_3 \to a_1+a_2,a_3$ so $S=a_1a_2(a_1+a_2)+(a_1+a_2)a_3(a_1+a_2+a_3) = (a_1+a_2)(a_1+a_3)(a_2+a_3)=(a_1+a_2+a_3)(a_1a_2+a_2a_3+a_3a_1)-a_1a_2a_3$ Now let it true for $n$ Let we have on board numbers $a_1,a_2,..a_n,a_{n+1}$ and first step is replacing $a_{n},a_{n+1}$ with $a_{n}+a_{n+1}$ We want to show, that final result $S$ will be same as $S_{n+1}$ In such case $S=a_na_{n+1}(a_n+a_{n+1})+(a_1+...+a_{n+1})( (a_n+a_{n+1})(a_1+a_2+...+a_{n-1})+a_1a_2+...+a_{n-2}a_{n-1})-((a_n+a_{n+1})(a_1a_2+...+a_{n-2}a_{n-1})+a_1a_2a_3+...+a_{n-3}a_{n-2}a_{n-1})=a_na_{n+1}(a_n+a_{n+1})+s_{n+1}(p_{n+1}-a_na_{n+1})-(q_{n+1}-a_na_{n+1}s_{n-1}) = S_{n+1} +a_na_{n+1}(a_n+a_{n+1})-a_na_{n+1}s_{n+1}+a_na_{n+1}s_{n-1}=S_{n+1}$ b) $s_n =1+2+...+n=\frac{n(n+1)}{2}$ $p_n=\frac{(1+2+...+n)^2-(1^2+2^2+...+n^2)}{2}=\frac{ (n-1)n(n+1)(3n+2)}{24}$ $q_n = \frac{(1+2+...+n)^3-3*(1+2+...+n)(1^2+2^2+...+n^2)+2(1^3+2^3+...+n^3)}{6}=\frac{n^2 (n+1)^2(n-1)(n-2)}{48}$ $S_n=s_np_n-q_n= \frac{(n-1)n^2(n+1)^2(3n+2)- (n-2)(n-1)n^2(n+1)^2}{48}= \frac{(n-1)n^2(n+1)^2(n+2)}{24}$
wassupevery1
01.01.2025 21:26
Let's solve when $50$ is replaced by $n \geq 2$.
They key here is the identity $(a+b)^3 = a^3+b^3 + 3ab(a+b)$, hence it is useful to consider the difference between the cube of sums and the sum of cubes.
Assume that the sum of the cubes of the numbers on the board so far is $A$, and the sum of the numbers on her notes so far is $S$. We claim that $A-3S$ does not change after any operation.
Let's assume the numbers on the board are $a_1, a_2, \ldots, a_m$. Then $A-3S = a_1^3+a_2^3+ a_3^3 + \cdots + a_m^3 - 3S$.
WLOG assume Anya then chooses $a_1, a_2$. Then $S$ increases by $a_1a_2(a_1+a_2)$, while the numbers on the board are now $a_1+a_2, a_3, \ldots, a_m$. Hence the new value of $A-3S$ is $$(a_1+a_2)^3 + a_3^3 + \cdots + a_m^3 - 3\left( S+a_1a_2(a_1+a_2) \right) = a_1^3+a_2^3+ a_3^3 + \cdots + a_m^3 - 3S,$$so any operation does not change this $A-3B$.
Let $A-3S = B$. Initially, $A = 1^3+2^3+ \cdots + n^3, S = 0$, so $B = 1^3+2^3+ \cdots + n^3$.
At the end, $B$ does not change, while $A = (1+2+ \cdots + n)^3$, so $$S = \frac{A-B}{3} = \frac{(1+2+ \cdots + n)^3-(1^3+2^3+ \cdots + n^3)}{3} = \frac{(n-1)n^2(n+1)^2(n+2)}{24},$$which does not depend on the order of Anya's actions.