Olympiad Maths Prep

Library / /22 of 55

Number theory Difficulty 5.7 AIME, harder Prove it Ukraine

Find all tuples of positive integers (m,n,k)(m, n, k) that satisfy the equation
(m!+m)(n!+n)=(k!+k). (m! + m)(n! + n) = (k! + k).

Solution

From the problem statement, it is obvious that k>mk > m and k>nk > n. We rewrite the given equation as
mn((m1)!+1)((n1)!+1)=k((k1)!+1). m n ((m-1)! + 1)((n-1)! + 1) = k ((k-1)! + 1).

Since (k1)!(k-1)! is divisible by mm and nn, (k1)!+1(k-1)! + 1 is not divisible by any factor of these numbers. Hence, kmnk \nmid m n. Suppose nmn \ge m. If m2m \ge 2, then
4(n!)24m!n!=(2m!)(2n!)(m!+m)(n!+n)=k!+k>(mn)!(2n)!4n!n!>(2n)(2n1)(n+1)n!4n!>(2n)(2n1)(n+1)4n(n1)(n2)21>(2n)(2n1)(2n2)(n+2)(n+1)4>2nn2n1n1n+11contradictions for n2. \begin{aligned} 4(n!)^2 &\ge 4 m! n! = (2 m!) (2 n!) \ge (m! + m)(n! + n) = k! + k > (m n)! \ge (2 n)! \\ 4 n! n! &> (2 n) \cdot (2 n - 1) \cdots (n + 1) \cdot n! \Rightarrow 4 n! > (2 n) \cdot (2 n - 1) \cdots (n + 1) \\ 4 n \cdot (n - 1) \cdot (n - 2) \cdots 2 \cdot 1 &> (2 n) \cdot (2 n - 1) \cdots (2 n - 2) \cdots (n + 2) \cdot (n + 1) \\ 4 &> \frac{2 n}{n} \cdot \frac{2 n - 1}{n - 1} \cdots \frac{n + 1}{1} \Rightarrow \text{contradictions for } n \ge 2. \end{aligned}
Let us show that for n2n \ge 2 this yields a contradiction. On the right-hand side, each factor except the first and last one is greater than the ones on the left. Now, let us show that the product of the first and last factors is still greater on the right-hand side: 4n1>(2n)(n+1)>6n4 n \cdot 1 > (2 n) \cdot (n + 1) > 6 n.

Therefore, there is only one option m=1m = 1, hence,
2n!+2n=k!+k(n+1)!+(n+1)>(n+1)!+nn>n!(n1)n=1m=1. 2 \cdot n! + 2 n = k! + k \ge (n + 1)! + (n + 1) > (n + 1)! + n \Rightarrow n > n! (n - 1) \Rightarrow n = 1 \Rightarrow m = 1.

Then, we easily get k=2k = 2.

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.