Maths Olympiad Prep

Library / Taiwan IMO Selection Camp /153 of 359

Taiwan IMO Selection Camp, 2022

Number theory Difficulty 5.6 AIME, harder Prove it Taiwan

Prove that there are only finitely many quadruples of positive integers (a,b,c,n)(a, b, c, n) for which the equality
n!=an−1+bn−1+cn−1 n! = a^{n-1} + b^{n-1} + c^{n-1}
holds.

Solution

For fixed nn there are clearly finitely many solutions; we will show that there is no solution with n>100n > 100. So assume n>100n > 100. By AM-GM inequality,
n!=2n(n−1)(n−2)(n−3)⋅(3⋅4⋯(n−4))≤2(n−1)4(3+⋯+(n−4)n−6)n−6=2(n−1)4(n−12)n−6<(n−12)n−1, \begin{aligned} n! &= 2n(n-1)(n-2)(n-3) \cdot (3 \cdot 4 \cdots (n-4)) \\ &\le 2(n-1)^4 \left( \frac{3 + \cdots + (n-4)}{n-6} \right)^{n-6} = 2(n-1)^4 \left( \frac{n-1}{2} \right)^{n-6} < \left( \frac{n-1}{2} \right)^{n-1}, \end{aligned}
thus a,b,c<n−12a, b, c < \frac{n-1}{2}.

For every prime pp and integer m≠0m \ne 0, let νp(m)\nu_p(m) denote the pp-adic valuation of mm; that is the greatest non-negative integer kk for which pkp^k divides mm. Legendre's formula states that
νp(n!)<∑s=1∞nps=np−1.(1) \nu_p(n!) < \sum_{s=1}^{\infty} \frac{n}{p^s} = \frac{n}{p-1}. \quad (1)
If nn is odd then an−1,bn−1,cn−1a^{n-1}, b^{n-1}, c^{n-1} are squares, and by considering them modulo 44 we conclude that a,b,ca, b, c must be even. hence, 2n−1∣n!2^{n-1} \mid n! but that is impossible for odd nn because ν2(n!)=ν2((n−1)!)<n−1\nu_2(n!) = \nu_2((n-1)!) < n-1 by (1). From now on we assume that nn is even. If all three numbers a+b,b+c,c+aa+b, b+c, c+a are powers of 22 then a,b,ca, b, c have the same parity. If they are all odd, then n!=an−1+bn−1+cn−1n! = a^{n-1}+b^{n-1}+c^{n-1} is also odd, contradicting the assumption that nn must be even. If all a,b,ca, b, c are divisible by 44, this contradicts ν2(n!)≤n−1\nu_2(n!) \le n-1. If, say, aa is not divisible by 44, then 2a=(a+b)+(a+c)−(b+c)2a = (a+b) + (a+c) - (b+c) is not divisible by 88, and since all a+b,b+c,c+aa+b, b+c, c+a are powers of 22 we get that one of these sums equals 44, so two of the numbers of a,b,ca, b, c are equal to 22. Say a=b=2a = b = 2, then c=2r−2c = 2^r - 2 and since c∣n!c \mid n!, we must have c∣an−1+bn−1=2nc \mid a^{n-1} + b^{n-1} = 2^n implying r=2r = 2, and so c=2c = 2, which is impossible because n!≡0≢3⋅2n−1(mod5)n! \equiv 0 \not\equiv 3 \cdot 2^{n-1} \pmod 5.

So now we assume that the sum of two numbers among a,b,ca, b, c, say a+ba+b, is not a power of 22, so it is divisible by some odd prime pp. Then p≤a+b<np \le a+b < n and so cn−1=n!−(an−1+bn−1)c^{n-1} = n! - (a^{n-1} + b^{n-1}) is divisible by pp. If pp divides aa and bb, we get pn−1∣n!p^{n-1} \mid n!,

contradicting (1). Next, using (1) and the Lifting the Exponent Lemma we get
νp(1)+νp(2)+⋯+νp(n)=νp(n!)=νp(n!−cn−1)=νp(an−1+bn−1)=νp(a+b)+νp(n−1).(2) \nu_p(1)+\nu_p(2)+\cdots+\nu_p(n) = \nu_p(n!) = \nu_p(n!-c^{n-1}) = \nu_p(a^{n-1}+b^{n-1}) = \nu_p(a+b)+\nu_p(n-1). \tag{2}
In view of (2), no number of 1,2,…,n1, 2, \dots, n can be divisible by pp, except a+ba+b and n−1>a+bn-1 > a+b. On the other hand, p∣cp|c implies that p<n/2p < n/2 and so there must be at least two such numbers. Hence, there are two multiples of pp among 1,2,…,n1, 2, \dots, n, namely a+b=pa+b = p and n−1=2pn-1 = 2p. But this is another contradiction because n−1n-1 is odd. This final contradiction shows that there is no solution of the equation for n>100n > 100.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge 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.