Maths Olympiad Prep

Library / /25 of 31

Combinatorics Difficulty 6.8 National olympiad Prove it Belarus

The numbers 1,2,,501, 2, \dots, 50 are written on the blackboard. Ann makes the following operations: she erases any two numbers aa and bb from the blackboard, writes down to the blackboard one number — the sum a+ba+b, afterwards she writes the number ab(a+b)ab(a+b) to her notebook. After 49 such operations when only one number left on the blackboard, Ann found the sum SS of all 49 numbers which she wrote to her notebook.

a) Prove that SS doesn't depend on the order of Ann's operations.

b) Find SS.

Solution

Let's see how, as a result of Ann's actions, the sum of the cubes of the numbers written on the board changes. The identity (a+b)3=a3+b3+3ab(a+b)(a+b)^3 = a^3 + b^3 + 3ab(a+b) implies that after each action of Ann, the sum of the cubes of all numbers written on the board increases by the number which is three times greater than the one that Ann writes down to her notebook. Therefore the sum of all numbers written in the notebook is equal to the difference between the cube of the last number remaining on the board and the sum of the cubes of all numbers written on the board initially. The number that remains on the board is equal to the sum of all numbers written on it initially which means that
3S=(1+2++50)3(13+23++503). 3S = (1 + 2 + \dots + 50)^3 - (1^3 + 2^3 + \dots + 50^3).
We use the well-known identity
13+23++n3=(1+2++n)2=(n(n+1)2)2, 1^3 + 2^3 + \dots + n^3 = (1 + 2 + \dots + n)^2 = \left(\frac{n(n+1)}{2}\right)^2,
which is easy to prove by induction. Since 50512=1275\frac{50 \cdot 51}{2} = 1275, then
3S=1275312752=127521274=342512741275. 3S = 1275^3 - 1275^2 = 1275^2 \cdot 1274 = 3 \cdot 425 \cdot 1274 \cdot 1275.
So the number SS is equal to 42512741275=690348750425 \cdot 1274 \cdot 1275 = 690348750.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.