Maths Olympiad Prep

Track / Stage 7 / 92 of 300 #2132 of 2604

Problem 2132

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 a1a2…an=b1b2…bn? 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 n≥3n \ge 3.

Assume n≥3n \ge 3. Let us introduce such denotations:
a1+a2+⋯+an−1=a,a1a2…an−1=A,b1+b2+⋯+bn−1=b,b1b2…bn−1=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=bn⇒a+an=b+AanB⇒Ban−Aan=bB−aB⇒an=B(b−a)B−A⇒bn=A(b−a)B−A.(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 2n−22n-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 (b−a)(b-a) and (B−A)(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(b−a)B−A=−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 2n−22n-2 numbers had products differing by 1, i.e. ∣B−A∣=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 n−1n-1 factors, and which are neighbouring positive integers. As the basis let us choose 2N−12^N - 1 and 2N2^N.
Let us choose numbers so that:
a1=221−1=3; a_1 = 2^{2^1} - 1 = 3;
a2=221+1=5, then a1a2=222−1; a_2 = 2^{2^1} + 1 = 5, \text{ then } a_1 a_2 = 2^{2^2} - 1;
a3=222+1=17, then a1a2a3=223−1;… a_3 = 2^{2^2} + 1 = 17, \text{ then } a_1 a_2 a_3 = 2^{2^3} - 1; \dots
an−2=22n−3+1, then a1a2…an−2=22n−2−1; a_{n-2} = 2^{2^{n-3}} + 1, \text{ then } a_1 a_2 \dots a_{n-2} = 2^{2^{n-2}} - 1;
an−1=22n−2+1, then a1a2…an−1=22n−1−1; 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=222−1; 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=223−1;… b_3 = 2^{2^2} = 16, \text{ then } b_1 b_2 b_3 = 2^{2^3 - 1}; \dots
bn−2=22n−3, then b1b2…bn−2=22n−2−1; b_{n-2} = 2^{2^{n-3}}, \text{ then } b_1 b_2 \dots b_{n-2} = 2^{2^{n-2}-1};
bn−1=22n−2+1, then b1b2…bn−1=22n−1. 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 b1b2…bn−1=B=22n−1b_1 b_2 \dots b_{n-1} = B = 2^{2^{n-1}}, a1a2…an−1=A=22n−1−1a_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+⋯+an−1=221−1+221+1+222+1+⋯+22n−3+1+22n−2+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+⋯+bn−1=220+221+⋯+22n−3+22n−2+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}.
b−a=220+221+⋯+22n−3+22n−2+1−221−221−222−⋯−22n−3−22n−2−(n−3)==220−221+22n−2+1−22n−2−(n−3)=22n−2−(n−1)>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 B−A=1B-A=1, we obtain
an=B(b−a)B−A=B(b−a)>bn=A(b−a)B−A=A(b−a)=(22n−1−1)(22n−2−(n−1))>bn−1=22n−2+1>an−1=22n−2+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 22n−1−1>22n−2+12^{2^{n-1}} - 1 > 2^{2^{n-2}+1}, and even a stronger inequality: 22n−1≥22n−2+22^{2^{n-1}} \ge 2^{2^{n-2}+2}. Then we have:
22n−1≥22n−2+2⇔2n−1≥2n−2+2⇔2n−2≥2. 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 t2−pt+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 2n−22n-2 pairwise different numbers a1,a2,…,an−1a_1, a_2, \dots, a_{n-1}, b1,b2,…,bn−1b_1, b_2, \dots, b_{n-1}, which satisfy the conditions:
a1+a2+⋯+an−1=a=b1+b2+⋯+bn−1−1,a1a2…an−1=A=b1b2…bn−1−1.(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 b−a=1b-a=1 and B−A=1B-A=1, therefore we can make a set of 2n2n pairwise different numbers a1,a2,…,an−1,an,b1,b2,…,bn−1,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 n≥2n \ge 2 obtain two sets of nn numbers, sums and products of which differ by 1.
Suppose 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} satisfy conditions (3). Let us add to them numbers: an=Aa_n = A and bn=A−1b_n = A-1. Then
a1+a2+⋯+an−1+an=a+A,b1+b2+⋯+bn−1+bn=a+1+A−1=a+A,a1a2…an−1an=AA=A2,b1b2…bn−1bn=(A+1)(A−1)=A2−1. 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=A2−2a_{n+1} = A^2 - 2 and bn+1=A2−1b_{n+1} = A^2 - 1 to these numbers and obtain:
a1+a2+⋯+an−1+an+an+1=a+A+A2−2,b1+b2+⋯+bn−1+bn+bn+1=a+A+A2−1,a1a2…an−1anan+1=A2⋅(A2−2)=A4−2A2,b1b2…bn−1bnbn+1=(A2−1)(A2−1)=A4−2A2+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 n≥3n \ge 3, and from existence of sets satisfying conditions (3) for n=3n=3 it follows that there are sets for any even n≥4n \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.