Maths Olympiad Prep

Track / Stage 6 / 217 of 400 #1697 of 2444

Problem 1697

National Olympiad, first round
Number theory Difficulty 6.3 Prove it Ukrainian National Mathematical Olympiad · Ukraine

For which values of n>1n > 1 is there a set of pairwise distinct natural numbers (a1,a2,...,an)(a_1, a_2, ..., a_n) such that the following condition is satisfied:
(a1+1)!+(a2+1)!+...+(an+1)!:a1!+a2!+...+an! (a_1+1)!+(a_2+1)!+...+(a_n+1)! : a_1!+a_2!+...+a_n!

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

a1,a2,...,ana_1, a_2, ..., a_n Without the loss of generality, let us assume that a1<a2<...<ana_1 < a_2 < ... < a_n. Then (ai+1)!ai!(an+1)(a_i + 1)! \le a_i!(a_n + 1), and equality is reached only when i=ni = n.

Let (a1+1)!+(a2+1)!+...+(an+1)!=N(a1!+a2!+...+an!)(a_1 + 1)! + (a_2 + 1)! + ... + (a_n + 1)! = N(a_1! + a_2! + ... + a_n!) for some natural number NN. Then the condition above yields Nan+1N \le a_n + 1, moreover, if n>1n > 1, then N<an+1N < a_n + 1.

Let now n>1n > 1, then we have that NanN \le a_n. Let us prove that it is impossible by showing that:
(a1+1)!+(a2+1)!+...+(an+1)!>an(a1!+a2!+...+an!) (a_1+1)!+(a_2+1)!+...+(a_n+1)! > a_n(a_1!+a_2!+...+a_n!)

Let's consider the following expression:
(a1+1)!+(a2+1)!+...+(an+1)!an(a1!+a2!+...+an!)=i=1nai!(ai+1an). (a_1+1)!+(a_2+1)!+...+(a_n+1)! - a_n(a_1!+a_2!+...+a_n!) = \sum_{i=1}^{n} a_i!(a_i+1-a_n).
The last term is equal to an!a_n!. If an1=an1a_{n-1} = a_n - 1, then the penultimate term is zero. It is enough to consider the following:
i=1nai!(ai+1an)i=1an1ai!(an1i)=i=1an2ai!(an1i) i=1an2i!an=ani=1an2i!an(an2)(an2)!<an!(a1+1)!+(a2+1)!+...+(an+1)!an(a1!+a2!+...+an!)>0, \begin{aligned} \sum_{i=1}^{n} a_i!(a_i+1-a_n) &\le \sum_{i=1}^{a_n-1} a_i!(a_n-1-i) = \sum_{i=1}^{a_n-2} a_i!(a_n-1-i) \ &\le \sum_{i=1}^{a_n-2} i!a_n = a_n \sum_{i=1}^{a_n-2} i! \le \\ a_n(a_n-2)(a_n-2)! < a_n! \Rightarrow \\ (a_1+1)!+(a_2+1)!+...+(a_n+1)! - a_n(a_1!+a_2!+...+a_n!) > 0, \end{aligned}
which yields the desired result. Hence, there are no such sets for n>1n > 1.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.