Maths Olympiad Prep

Library / Ukrainian National Mathematical Olympiad /78 of 201

Ukrainian National Mathematical Olympiad

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((m−1)!+1)((n−1)!+1)=k((k−1)!+1). m n ((m-1)! + 1)((n-1)! + 1) = k ((k-1)! + 1).

Since (k−1)!(k-1)! is divisible by mm and nn, (k−1)!+1(k-1)! + 1 is not divisible by any factor of these numbers. Hence, k∤mnk \nmid m n. Suppose n≥mn \ge m. If m≥2m \ge 2, then
4(n!)2≥4m!n!=(2m!)(2n!)≥(m!+m)(n!+n)=k!+k>(mn)!≥(2n)!4n!n!>(2n)⋅(2n−1)⋯(n+1)⋅n!⇒4n!>(2n)⋅(2n−1)⋯(n+1)4n⋅(n−1)⋅(n−2)⋯2⋅1>(2n)⋅(2n−1)⋯(2n−2)⋯(n+2)⋅(n+1)4>2nn⋅2n−1n−1⋯n+11⇒contradictions for n≥2. \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 n≥2n \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: 4n⋅1>(2n)⋅(n+1)>6n4 n \cdot 1 > (2 n) \cdot (n + 1) > 6 n.

Therefore, there is only one option m=1m = 1, hence,
2⋅n!+2n=k!+k≥(n+1)!+(n+1)>(n+1)!+n⇒n>n!(n−1)⇒n=1⇒m=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.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.