Maths Olympiad Prep

Track / Stage 7 / 92 of 300 #1972 of 2444

Problem 1972

National Olympiad second round; IMO P1/P4
Algebra Difficulty 7.3 Prove it UkraineMO · Ukraine

For which positive integers nn there exist 2n2n pairwise different positive integers a1,a2,,ana_1, a_2, \dots, a_n and b1,b2,,bnb_1, b_2, \dots, b_n satisfying the equations:
a1+a2++an=b1+b2++bn and a1a2an=b1b2bn? a_1 + a_2 + \dots + a_n = b_1 + b_2 + \dots + b_n \text{ and } a_1 a_2 \dots a_n = b_1 b_2 \dots b_n?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Answer: for all n3n \ge 3.

Assume n3n \ge 3. Let us introduce such denotations:
a1+a2++an1=a,a1a2an1=A,b1+b2++bn1=b,b1b2bn1=B.(1) a_1 + a_2 + \dots + a_{n-1} = a, \quad a_1 a_2 \dots a_{n-1} = A, \quad b_1 + b_2 + \dots + b_{n-1} = b, \quad b_1 b_2 \dots b_{n-1} = B. \quad (1)
Then we can write that a+an=b+bna + a_n = b + b_n, Aan=BbnA a_n = B b_n, and hence,
AanB=bna+an=b+AanBBanAan=bBaBan=B(ba)BAbn=A(ba)BA.(2) \begin{aligned} \frac{A a_n}{B} &= b_n \Rightarrow a + a_n = b + \frac{A a_n}{B} \Rightarrow B a_n - A a_n = b B - a B \Rightarrow \\ a_n &= \frac{B(b-a)}{B-A} \Rightarrow b_n = \frac{A(b-a)}{B-A}. \end{aligned} \quad (2)
Thus, having a set of 2n22n-2 numbers that satisfy conditions (1), one can always add numbers ana_n and bnb_n determined by formulas (2). Then a set of 2n2n numbers satisfies the condition if and only if the signs of the numbers (ba)(b-a) and (BA)(B-A) are the same.
As an example of the opposite, consider the numbers a1=3,a2=5,b1=2,b2=7a_1 = 3, a_2 = 5, b_1 = 2, b_2 = 7. Then a=8,b=9,A=15,B=14a=8, b=9, A=15, B=14. Then a3=B(ba)BA=14,b3=15a_3 = \frac{B(b-a)}{B-A} = -14, b_3 = -15. Indeed, the sets of numbers
3; 5; -14 and 2; 7; -15 have the same sums and products, but are constituted by not only positive integers.

The easiest way is to choose numbers such that the first 2n22n-2 numbers had products differing by 1, i.e. BA=1|B-A|=1. Then numbers found by formulas (2) will be integer, and if they satisfy other conditions, they will meet the conditions of the problem. Thus let us find two numbers, each of which has a different decomposition into at least n1n-1 factors, and which are neighbouring positive integers. As the basis let us choose 2N12^N - 1 and 2N2^N.
Let us choose numbers so that:
a1=2211=3; a_1 = 2^{2^1} - 1 = 3;
a2=221+1=5, then a1a2=2221; a_2 = 2^{2^1} + 1 = 5, \text{ then } a_1 a_2 = 2^{2^2} - 1;
a3=222+1=17, then a1a2a3=2231; a_3 = 2^{2^2} + 1 = 17, \text{ then } a_1 a_2 a_3 = 2^{2^3} - 1; \dots
an2=22n3+1, then a1a2an2=22n21; a_{n-2} = 2^{2^{n-3}} + 1, \text{ then } a_1 a_2 \dots a_{n-2} = 2^{2^{n-2}} - 1;
an1=22n2+1, then a1a2an1=22n11; a_{n-1} = 2^{2^{n-2}} + 1, \text{ then } a_1 a_2 \dots a_{n-1} = 2^{2^{n-1}} - 1;
b1=220=2; b_1 = 2^{2^0} = 2;
b2=221=4, then b1b2=220+21=2221; b_2 = 2^{2^1} = 4, \text{ then } b_1 b_2 = 2^{2^0 + 2^1} = 2^{2^2 - 1};
b3=222=16, then b1b2b3=2231; b_3 = 2^{2^2} = 16, \text{ then } b_1 b_2 b_3 = 2^{2^3 - 1}; \dots
bn2=22n3, then b1b2bn2=22n21; b_{n-2} = 2^{2^{n-3}}, \text{ then } b_1 b_2 \dots b_{n-2} = 2^{2^{n-2}-1};
bn1=22n2+1, then b1b2bn1=22n1. b_{n-1} = 2^{2^{n-2}+1}, \text{ then } b_1 b_2 \dots b_{n-1} = 2^{2^{n-1}}.
Due to the construction we have that b1b2bn1=B=22n1b_1 b_2 \dots b_{n-1} = B = 2^{2^{n-1}}, a1a2an1=A=22n11a_1 a_2 \dots a_{n-1} = A = 2^{2^{n-1}} - 1. What is left to check other conditions. B=A+1>AB = A+1 > A, hence it should be true that b>ab > a.
a=a1+a2++an1=2211+221+1+222+1++22n3+1+22n2+1, a = a_1 + a_2 + \dots + a_{n-1} = 2^{2^1} - 1 + 2^{2^1} + 1 + 2^{2^2} + 1 + \dots + 2^{2^{n-3}} + 1 + 2^{2^{n-2}} + 1,
b=b1+b2++bn1=220+221++22n3+22n2+1. b = b_1 + b_2 + \dots + b_{n-1} = 2^{2^0} + 2^{2^1} + \dots + 2^{2^{n-3}} + 2^{2^{n-2}+1}.
ba=220+221++22n3+22n2+122122122222n322n2(n3)==220221+22n2+122n2(n3)=22n2(n1)>0 b-a = 2^{2^0} + 2^{2^1} + \dots + 2^{2^{n-3}} + 2^{2^{n-2}+1} - 2^{2^1} - 2^{2^1} - 2^{2^2} - \dots - 2^{2^{n-3}} - 2^{2^{n-2}} - (n-3) = \\ = 2^{2^0} - 2^{2^1} + 2^{2^{n-2}+1} - 2^{2^{n-2}} - (n-3) = 2^{2^{n-2}} - (n-1) > 0
The last inequality can be proved easily by Mathematical Induction.
It remains to check that the numbers are pairwise different. I.e., that the added numbers ana_n and bnb_n do not equal any of the numbers constructed earlier. Provided that BA=1B-A=1, we obtain
an=B(ba)BA=B(ba)>bn=A(ba)BA=A(ba)=(22n11)(22n2(n1))>bn1=22n2+1>an1=22n2+1. a_n = \frac{B(b-a)}{B-A} = B(b-a) > b_n = \frac{A(b-a)}{B-A} = A(b-a) = (2^{2^{n-1}} - 1)(2^{2^{n-2}} - (n-1)) > \\ b_{n-1} = 2^{2^{n-2}+1} > a_{n-1} = 2^{2^{n-2}} + 1.
Let us prove that 22n11>22n2+12^{2^{n-1}} - 1 > 2^{2^{n-2}+1}, and even a stronger inequality: 22n122n2+22^{2^{n-1}} \ge 2^{2^{n-2}+2}. Then we have:
22n122n2+22n12n2+22n22. 2^{2^{n-1}} \ge 2^{2^{n-2}+2} \Leftrightarrow 2^{n-1} \ge 2^{n-2} + 2 \Leftrightarrow 2^{n-2} \ge 2.
For n=1n=1 it is clear that such numbers do not exist.

For n=2n=2, if a1a2=b1b2=qa_1 a_2 = b_1 b_2 = q and a1+a2=b1+b2=pa_1 + a_2 = b_1 + b_2 = p, then the numbers a1,a2a_1, a_2 and b1,b2b_1, b_2 are the roots of the square equation t2pt+q=0t^2 - p t + q = 0, and therefore these pairs of numbers are the same up to the order.

Alternative solution.
Suppose we have 2n22n-2 pairwise different numbers a1,a2,,an1a_1, a_2, \dots, a_{n-1}, b1,b2,,bn1b_1, b_2, \dots, b_{n-1}, which satisfy the conditions:
a1+a2++an1=a=b1+b2++bn11,a1a2an1=A=b1b2bn11.(3) a_1 + a_2 + \dots + a_{n-1} = a = b_1 + b_2 + \dots + b_{n-1} - 1, \quad a_1 a_2 \dots a_{n-1} = A = b_1 b_2 \dots b_{n-1} - 1. \quad (3)
Thus, for the formulas (2) we have ba=1b-a=1 and BA=1B-A=1, therefore we can make a set of 2n2n pairwise different numbers a1,a2,,an1,an,b1,b2,,bn1,bna_1, a_2, \dots, a_{n-1}, a_n, b_1, b_2, \dots, b_{n-1}, b_n by adding two numbers obtained by the formulas (2), an=B=A+1a_n = B = A+1 and bn=Ab_n = A.
What is left is to understand how for every positive integer n2n \ge 2 obtain two sets of nn numbers, sums and products of which differ by 1.
Suppose pairwise different numbers a1,a2,,an1,b1,b2,,bn1a_1, a_2, \dots, a_{n-1}, b_1, b_2, \dots, b_{n-1} satisfy conditions (3). Let us add to them numbers: an=Aa_n = A and bn=A1b_n = A-1. Then
a1+a2++an1+an=a+A,b1+b2++bn1+bn=a+1+A1=a+A,a1a2an1an=AA=A2,b1b2bn1bn=(A+1)(A1)=A21. a_1 + a_2 + \dots + a_{n-1} + a_n = a + A, \quad b_1 + b_2 + \dots + b_{n-1} + b_n = a + 1 + A - 1 = a + A, \\ a_1 a_2 \dots a_{n-1} a_n = A A = A^2, \quad b_1 b_2 \dots b_{n-1} b_n = (A+1)(A-1) = A^2 - 1.
Now let us add an+1=A22a_{n+1} = A^2 - 2 and bn+1=A21b_{n+1} = A^2 - 1 to these numbers and obtain:
a1+a2++an1+an+an+1=a+A+A22,b1+b2++bn1+bn+bn+1=a+A+A21,a1a2an1anan+1=A2(A22)=A42A2,b1b2bn1bnbn+1=(A21)(A21)=A42A2+1. a_1 + a_2 + \dots + a_{n-1} + a_n + a_{n+1} = a + A + A^2 - 2, \\ b_1 + b_2 + \dots + b_{n-1} + b_n + b_{n+1} = a + A + A^2 - 1, \\ a_1 a_2 \dots a_{n-1} a_n a_{n+1} = A^2 \cdot (A^2 - 2) = A^4 - 2A^2, \\ b_1 b_2 \dots b_{n-1} b_n b_{n+1} = (A^2 - 1)(A^2 - 1) = A^4 - 2A^2 + 1.
As you can see, we made sets of 2n+22n+2 pairwise different numbers a1,a2,,an+1,b1,b2,,bn+1a_1, a_2, \dots, a_{n+1}, b_1, b_2, \dots, b_{n+1}, that satisfy conditions (3), therefore from them one can obtain the desired sets of 2n+42n+4 numbers. Thus, from the existence of sets satisfying conditions (3) for n=2n=2, we obtain that there are desired sets of numbers for any odd n3n \ge 3, and from existence of sets satisfying conditions (3) for n=3n=3 it follows that there are sets for any even n4n \ge 4. What is left is to state these numbers.
For n=2n=2 we can take a1=4,a2=5,b1=3,b2=7a_1 = 4, a_2 = 5, b_1 = 3, b_2 = 7,
For n=3n=3 we can take a1=2,a2=3,a3=15,b1=1,b2=7,b3=13a_1 = 2, a_2 = 3, a_3 = 15, b_1 = 1, b_2 = 7, b_3 = 13.
Then, e.g., we make sets as follows:
For n=3n=3: a1=4,a2=5,a3=21a_1 = 4, a_2 = 5, a_3 = 21 and b1=3,b2=7,b3=20b_1 = 3, b_2 = 7, b_3 = 20.
With the set for n=2n=2 satisfying conditions (3), we now make a set for n=4n=4 that also satisfies the conditions (3):
a1=4,a2=5,a3=20,a4=398 and b1=3,b2=7,b3=19,b4=399. Then we have thata1+a2+a3+a4=427,b1+b2+b3+b4=428, anda1a2a3a4=159200,b1b2b3b4=159201. a_1 = 4, a_2 = 5, a_3 = 20, a_4 = 398 \text{ and } b_1 = 3, b_2 = 7, b_3 = 19, b_4 = 399. \text{ Then we have that} \\ a_1 + a_2 + a_3 + a_4 = 427, b_1 + b_2 + b_3 + b_4 = 428, \text{ and} \\ a_1 a_2 a_3 a_4 = 159200, b_1 b_2 b_3 b_4 = 159201.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.