Maths Olympiad Prep

Library / /48 of 52

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Belarus

The numbers 1,2,,49,501, 2, \dots, 49, 50 are written on the blackboard. Ann performs the following operations: she chooses three arbitrary numbers a,b,ca, b, c from the board, replaces them by their sum a+b+ca + b + c and writes the number (a+b)(b+c)(c+a)(a + b)(b + c)(c + a) to her notebook. Ann performs such operations until only two numbers remain on the board (in total 24 operations). Then she calculates the sum of all 24 numbers written in the notebook. Let AA and BB be the maximum and the minimum possible sums that Ann can obtain.
Find the value of AB\frac{A}{B}.

Solution

Answer: AB=4\frac{A}{B} = 4.

(Solution by P. Verigo.) Let us solve the problem in more general case. Replace 5050 by an arbitrary positive integer n>2n > 2 of the form n=4k+2n = 4k + 2 and let the numbers initially written on the blackboard be 1,2,,n1,n1, 2, \dots, n-1, n.

For any \ell numbers a1,a2,,aa_1, a_2, \dots, a_\ell written on the blackboard consider its characteristic defined by
f(a1,a2,,a)=13((a1+a2++a)3a13a23a3). f(a_1, a_2, \dots, a_\ell) = \frac{1}{3}\left((a_1 + a_2 + \dots + a_\ell)^3 - a_1^3 - a_2^3 - \dots - a_\ell^3\right).
Let f0f_0 be the characteristic of the initial numbers on the blackboard and fmf_m be the characteristic of the numbers written after mm operations. It is easy to see that
(a+b)(b+c)(c+a)=13((a+b+c)3a3b3c3). (a+b)(b+c)(c+a) = \frac{1}{3}\left((a+b+c)^3 - a^3 - b^3 - c^3\right).
Hence at the mthm^{\text{th}} operation Ann writes to her notebook the difference fm1fmf_{m-1} - f_m. Therefore, the sum XX of all numbers written in the notebook after n22\frac{n-2}{2} operations equals to
f0fn22=13(S3(13+23++n3))Sx(Sx), f_0 - f_{\frac{n-2}{2}} = \frac{1}{3}(S^3 - (1^3 + 2^3 + \dots + n^3)) - S \cdot x \cdot (S-x),
where S=1+2++nS = 1 + 2 + \dots + n, and the two numbers: xx and SxS-x remain on the blackboard.

It is known that 13+23++n3=(1+2++n)21^3 + 2^3 + \dots + n^3 = (1 + 2 + \dots + n)^2, so X=13(S3S2)Sx(Sx)X = \frac{1}{3}(S^3 - S^2) - S \cdot x(S-x).

Note that S=(2k+1)(4k+3)S = (2k + 1)(4k + 3) is odd. Hence maxx(Sx)=s12s+12=s214\max x(S-x) = \frac{s-1}{2} \cdot \frac{s+1}{2} = \frac{s^2-1}{4} and minx(sx)=1(s1)=s1\min x(s-x) = 1 \cdot (s-1) = s-1.

Therefore the maximum possible sum equals
A=13(S3S2)S(S1)=13S(S1)(S3), A = \frac{1}{3}(S^3 - S^2) - S(S-1) = \frac{1}{3}S(S-1)(S-3),
the minimum possible sum equals
B=13(S3S2)S(S21)4=112S(S1)(S3), B = \frac{1}{3}(S^3 - S^2) - \frac{S(S^2 - 1)}{4} = \frac{1}{12}S(S-1)(S-3),
and clearly AB=4\frac{A}{B} = 4.

It remains to verify that Ann can leave on the blackboard the numbers x=s12x = \frac{s-1}{2} and y=s+12y = \frac{s+1}{2}. It is sufficient to divide the set {1,2,,4k+2}\{1, 2, \dots, 4k + 2\} into two groups the sums of numbers in which differ by 11. Consider the first group containing all odd numbers: {1,3,,4k+1}\{1, 3, \dots, 4k + 1\} and the second group containing all even numbers: {2,4,,4k+2}\{2, 4, \dots, 4k + 2\}. The difference of their sums equals 2k+12k + 1. Then we move the number kk from the second group to the first one if kk is even and the number k+1k + 1 from the second to the first if kk is odd. Thus the solution is finished.

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.