Maths Olympiad Prep

Library / /108 of 520

Number theory Difficulty 5.8 AIME, harder Find the answer

Find all integers n1n \geqslant 1 having the following property: there exists a permutation d1,d2,,dkd_{1}, d_{2}, \ldots, d_{k} of the positive divisors of nn such that, for all iki \leqslant k, the sum d1+d2++did_{1}+d_{2}+\ldots+d_{i} is a perfect square.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let nn be one of the sought integers, and d1,d2,,dkd_{1}, d_{2}, \ldots, d_{k} an appropriate permutation of the positive divisors of nn. For any integer iki \leqslant k, we set si=d1+d2++dis_{i}=\sqrt{d_{1}+d_{2}+\ldots+d_{i}}. We say that an integer \ell is good if si=is_{i}=i and di=2i1d_{i}=2 i-1 for all ii \leqslant \ell. Below, we will prove that every integer k\ell \leqslant k is good.
First, for any integer i2i \geqslant 2, we already note that

di=si2si12=(sisi1)(si+si1)si+si12. d_{i}=s_{i}^{2}-s_{i-1}^{2}=\left(s_{i}-s_{i-1}\right)\left(s_{i}+s_{i-1}\right) \geqslant s_{i}+s_{i-1} \geqslant 2 .

Consequently, d1=s1=1d_{1}=s_{1}=1.
Now consider a good integer k1\ell \leqslant k-1. We will prove that +1\ell+1 is also good. Indeed, if s+1+ss_{\ell+1}+s_{\ell} divides (s+1s)(s+1+s)=d+1\left(s_{\ell+1}-s_{\ell}\right)\left(s_{\ell+1}+s_{\ell}\right)=d_{\ell+1}, then it divides nn. Therefore, there exists an integer mm such that

dm=s+1+s2s+12+1 d_{m}=s_{\ell+1}+s_{\ell} \geqslant 2 s_{\ell}+1 \geqslant 2 \ell+1

Since dm>did_{m}>d_{i} for all ii \leqslant \ell, we deduce that m+1m \geqslant \ell+1. But then

s+1+s=dm=(smsm1)(sm+sm1)(smsm1)(s+1+s)s+1+s s_{\ell+1}+s_{\ell}=d_{m}=\left(s_{m}-s_{m-1}\right)\left(s_{m}+s_{m-1}\right) \geqslant\left(s_{m}-s_{m-1}\right)\left(s_{\ell+1}+s_{\ell}\right) \geqslant s_{\ell+1}+s_{\ell}

The inequalities are therefore equalities, which means that sm+sm1=s+1+ss_{m}+s_{m-1}=s_{\ell+1}+s_{\ell}, and that m=+1m=\ell+1, and that smsm1=1s_{m}-s_{m-1}=1, i.e., s+1=s+1=+1s_{\ell+1}=s_{\ell}+1=\ell+1. We conclude that

d+1=(s+1s)(s+1+s)=2+1 d_{\ell+1}=\left(s_{\ell+1}-s_{\ell}\right)\left(s_{\ell+1}+s_{\ell}\right)=2 \ell+1

which means as expected that +1\ell+1 is good.
In conclusion, the divisors of nn are the integers 1,3,,2k11,3, \ldots, 2 k-1. Conversely, if the divisors of nn are the integers 1,3,,2k11,3, \ldots, 2 k-1, the integer nn certainly fits.
In particular, if k2k \geqslant 2, the integer dk1d_{k-1} is an odd divisor of ndk1=2n-d_{k-1}=2, so dk1=1d_{k-1}=1 and k=2k=2. Thus, either k=1k=1, in which case n=1n=1, or k=2k=2, in which case n=3n=3. In both cases, these values of nn fit. The sought integers are therefore n=1n=1 and n=3n=3.

Comment from the graders: This problem was rather difficult and was solved in its entirety by very few students: only about ten students obtained full marks.
However, many students were able to earn points by trying to determine what the first divisors of the permutation should be. Many students, for example, obtain d1=1,d2=3,d3=5d_{1}=1, d_{2}=3, d_{3}=5, but "dare not 2^{2} continue by attempting induction to show that di=2i1d_{i}=2 i-1. Some want to conclude directly, which is not possible here, and many papers end abruptly and without any justification with: "we deduce that 1 and 3 are the only solutions". It is important to be aware that this kind of bluff is rarely rewarding.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.