Maths Olympiad Prep

Library / /220 of 397

, 2022

Number theory Difficulty 6.0 National Olympiad Prove it Taiwan

Find all positive integers nn with the following property: there exists a permutation (d1,d2,,dk)(d_1, d_2, \dots, d_k) of all nn positive divisors of nn (there are kk of them in total) such that for every i=1,2,,ki = 1, 2, \dots, k, the integer j=1idj=d1++di\sum_{j=1}^{i} d_j = d_1 + \dots + d_i is always a perfect square.

Solution

The answer is n=1,3n = 1, 3.
For i=1,2,,ki = 1, 2, \dots, k let d1++di=si2d_1 + \dots + d_i = s_i^2, and define s0=0s_0 = 0 as well. Obviously
0=s0<s1<s2<<sk0 = s_0 < s_1 < s_2 < \dots < s_k, so siis_i \ge i and
di=si2si12=(si+si1)(sisi1)si+si12i1.(1) d_i = s_i^2 - s_{i-1}^2 = (s_i + s_{i-1})(s_i - s_{i-1}) \ge s_i + s_{i-1} \ge 2i - 1. \quad (1)
The number 1 is one of the divisors, hence we must have d1=1d_1 = 1.
Consider d2d_2 and s22s_2 \ge 2. By definition, d2=s221=(s21)(s2+1)d_2 = s_2^2 - 1 = (s_2 - 1)(s_2 + 1), so the numbers s21s_2 - 1 and s2+1s_2 + 1 are divisors of nn. In particular, there is some index jj such that dj=s2+1d_j = s_2 + 1.
Notice that
s2+s1=s2+1=djsj+sj1;(2) s_2 + s_1 = s_2 + 1 = d_j \ge s_j + s_{j-1}; \qquad (2)
since the sequence s0<s1<<sks_0 < s_1 < \dots < s_k increases, the index jj cannot be greater than 2. Hence, the divisors s21s_2 - 1 and s2+1s_2 + 1 are listed among d1d_1 and d2d_2. Thus s21=d1=1s_2 - 1 = d_1 = 1 and s2+1=d2s_2 + 1 = d_2; therefore, s2=2s_2 = 2 and d2=3d_2 = 3. By repeating the above procedure, we can prove that di=2i1d_i = 2i - 1 and si=is_i = i for i=1,2,,ki = 1, 2, \dots, k.
Suppose we already have dj=2j1d_j = 2j - 1 and sj=js_j = j for all jij \ge i. Consider di+1=si+12si2=si+12i2=(si+1i)(si+1+i)d_{i+1} = s_{i+1}^2 - s_i^2 = s_{i+1}^2 - i^2 = (s_{i+1} - i)(s_{i+1} + i), the number si+1+is_{i+1} + i is a divisor of nn, so there is some index jj such that dj=si+1+id_j = s_{i+1} + i.
Similarly to (2), by (1) we have
si+1+si=si+1+i=djsj+sj1(3) s_{i+1} + s_i = s_{i+1} + i = d_j \ge s_j + s_{j-1} \qquad (3)
since the sequence s0<s1<<sks_0 < s_1 < \dots < s_k increases, (3) forces ji+1j \le i + 1. On the other hand, dj=si+1+i>2i>di>di1>>d1d_j = s_{i+1} + i > 2i > d_i > d_{i-1} > \dots > d_1, so ji+1j \le i + 1 is not possible. The only possibility is j=i+1j = i + 1.

si+1+i=di+1=si+12si2=si+12i2;si+12si+1=i(i+1). \begin{aligned} s_{i+1} + i &= d_{i+1} = s_{i+1}^2 - s_i^2 = s_{i+1}^2 - i^2; \\ s_{i+1}^2 - s_{i+1} &= i(i+1). \end{aligned}
By solving the equation, we get si+1=i+1s_{i+1} = i + 1 and di+1=2i+1d_{i+1} = 2i + 1.
As a result, the divisors of the number nn must be 1,3,,n2,n1, 3, \dots, n-2, n and dk=2k1=nd_k = 2k-1 = n, which is an odd number. Observe that dk1=n2d_{k-1} = n-2 is a divisor of nn, so we have n4n \le 4. Thus the only possible nn is 1 or 3. Can easily check both satisfies the desired property.

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 translated into English from zh; metadata (topic, difficulty) added by this project.