Olympiad Maths Prep

Library / /6 of 6

Number theory Difficulty 7.4 National olympiad, round 2 Prove it Argentina

We say a sequence a1,a2,a3,a_1, a_2, a_3, \dots of positive integers is *alagoana* if, for every positive integer nn, the following two conditions hold simultaneously:
* an!=a1a2ana_{n!} = a_1 \cdot a_2 \cdot \dots \cdot a_n.
* ana_n is the nnth power of a positive integer.
Determine all the sequences that are *alagoanas*.
(Note that n!=123nn! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n. For example, 4!=1234=244! = 1 \cdot 2 \cdot 3 \cdot 4 = 24. Thus, our sequence satisfies, for example, a24=a4!=a1a2a3a4a_{24} = a_{4!} = a_1 \cdot a_2 \cdot a_3 \cdot a_4.)

Solution

In order to do this, we will show that if the sequence is *alagoana*, then ana_n cannot have any prime factor.
Consider a prime pp. For every positive integer nn, let α(n)\alpha(n) be the exponent of pp in the factorization of ana_n. We will prove that α(n)=0\alpha(n) = 0 for every nn.
By the second condition on the sequence, we know that α(n)\alpha(n) is a multiple of nn; that is, there exists a non-negative integer knk_n such that α(n)=nkn\alpha(n) = n \cdot k_n. From the first condition, we have that an!=a1a2ana_{n!} = a_1 \cdot a_2 \cdot \dots \cdot a_n. This implies that α(n!)=α(1)+α(2)++α(n)\alpha(n!) = \alpha(1) + \alpha(2) + \dots + \alpha(n). In particular, α(n!)=α(n)+α((n1)!)\alpha(n!) = \alpha(n) + \alpha((n-1)!), so α(n)=α(n!)α((n1)!)\alpha(n) = \alpha(n!) - \alpha((n-1)!), that is, nkn=n!kn!(n1)!k(n1)!n \cdot k_n = n! \cdot k_{n!} - (n-1)! \cdot k_{(n-1)!}. Defining β(n)=(n1)!\beta(n) = (n-1)!, we have
kn=β(n)n(nkn!kβ(n)).(1) k_n = \frac{\beta(n)}{n} (n \cdot k_{n!} - k_{\beta(n)}). \qquad (1)
For n4n \ge 4, we will show, recursively, that βj(n)\beta^j(n) divides α(n)\alpha(n) for every positive integer jj, where βj(n)\beta^j(n) is the function β\beta applied jj times. To this end, we will apply formula (1) recursively. We first establish some facts we will use.
Let γm=β(m!)m!\gamma_m = \frac{\beta(m!)}{m!} be the factor appearing in formula (1) when applied to n=m!n = m!. Note that, for m3m \ge 3, γm\gamma_m is an integer (since m!1>mm! - 1 > m) and divides km!k_{m!}. In addition, γm\gamma_m divides γm+1\gamma_{m+1}, since ((m+1)!1)!(m+1)!=1m+1((m+1)!1)((m+1)!2)m!(m!1)!m!\frac{((m+1)!-1)!}{(m+1)!} = \frac{1}{m+1} \cdot ((m+1)! - 1) ((m+1)! - 2) \cdots m! \cdot \frac{(m!-1)!}{m!}, and (m+1)!(m+1)=(m+1)(m!1)>m!(m+1)! - (m+1) = (m+1)(m! - 1) > m!; then, γm\gamma_m divides γn\gamma_n for every n>m3n > m \ge 3. Now, we will prove recursively that, for every positive integer jj, we have that
kn=βj(n)nNj. k_n = \frac{\beta^j(n)}{n} \cdot N_j.
where NjN_j is an integer that can be expressed as a sum of 2j2^j multiples of integers of the form km!k_{m!}, where the smallest subindex m!m! that appears is βj(n)\beta^j(n).
For j=1j=1, the statement is clear from identity (1), since β(n)=(n1)!\beta(n) = (n-1)!.
Assume the result holds for j1j \ge 1. Since every term in the expression of NjN_j is a multiple of km!k_{m!} for an integer mm, and the smallest of the integers mm involved is βj1(n)1\beta^{j-1}(n) - 1 (since, by definition, βj(n):=(βj1(n)1)!\beta^j(n) := (\beta^{j-1}(n) - 1)!), it follows that each term is a multiple of γβj1(n)1=β((βj1(n)1)!)(βj1(n)1)!=βj+1(n)βj(n)\gamma_{\beta^{j-1}(n)-1} = \frac{\beta((\beta^{j-1}(n)-1)!)}{(\beta^{j-1}(n)-1)!} = \frac{\beta^{j+1}(n)}{\beta^j(n)}. Moreover, as a consequence of identity (1) applied to m!m!, the quotient in the division of km!k_{m!} by γβj1(n)1\gamma_{\beta^{j-1}(n)-1} can be written as a sum of a multiple of k(m!)!k_{(m!)!} and a multiple of kβ(m!)k_{\beta(m!)}. Then, NjN_j is a multiple of βj+1(n)βj(n)\frac{\beta^{j+1}(n)}{\beta^j(n)}, and the quotient Nj+1N_{j+1} can be expressed as a sum of 2j+12^{j+1} terms that are multiples of integers of the form km!k_{m!}, where the smallest subindex that appears is β(βj(n))=βj+1(n)\beta(\beta^j(n)) = \beta^{j+1}(n) (note that, if m1>m2m_1 > m_2, then m1!>β(m1)=(m11)!m2!>(m21)!=β(m2)m_1! > \beta(m_1) = (m_1 - 1)! \ge m_2! > (m_2 - 1)! = \beta(m_2)). We conclude that
kn=βj(n)nNj=βj(n)βj+1(n)nβj(n)Nj+1=βj+1(n)nNj+1, k_n = \frac{\beta^j(n)}{n} \cdot N_j = \frac{\beta^j(n) \beta^{j+1}(n)}{n \beta^j(n)} \cdot N_{j+1} = \frac{\beta^{j+1}(n)}{n} \cdot N_{j+1},
as we wanted to prove.
Thus, if n4n \ge 4, for every positive integer jj, we can write α(n)=nkn=βj(n)Nj\alpha(n) = n \cdot k_n = \beta^j(n) \cdot N_j for a non-negative integer NjN_j.
Finally, to conclude that α(n)=0\alpha(n) = 0 for all n4n \ge 4, we notice that βj(n)>2j\beta^j(n) > 2^j for every jj; for j=1j = 1, β(n)=(n1)!6>2\beta(n) = (n - 1)! \ge 6 > 2, since n4n \ge 4, and for j1j \ge 1, βj+1(n)βj(n)=(m1)!m2\frac{\beta^{j+1}(n)}{\beta^j(n)} = \frac{(m - 1)!}{m} \ge 2, since (m1)!2m(m - 1)! \ge 2m for every integer m4m \ge 4.
The remaining cases follow now easily from the identity α(1)+α(2)+α(3)=α(3!)=α(6)=0\alpha(1) + \alpha(2) + \alpha(3) = \alpha(3!) = \alpha(6) = 0, which implies that α(1)=α(2)=α(3)=0\alpha(1) = \alpha(2) = \alpha(3) = 0.

Looking for a route rather than 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.