Olympiad Maths Prep

Track / Stage 7 / 254 of 300 #1654 of 2000

Problem 1654

National olympiad second round; IMO P1/P4
Number theory Difficulty 7.6 Prove it

Example 3 Let the function f:NNf: \mathbf{N}^{*} \rightarrow \mathbf{N}^{*} be defined as follows: Let
(2n)!n!(n+1000)!=A(n)B(n)\frac{(2 n)!}{n!(n+1000)!}=\frac{A(n)}{B(n)}

where nN,A(n),B(n)n \in \mathbf{N}^{*}, A(n), B(n) are coprime positive integers. If B(n)=1B(n)=1, then f(n)=1f(n)=1; if B(n)>1B(n)>1, then f(n)f(n) is the largest prime factor of B(n)B(n).

Prove: The function ff is a bounded function, and find the maximum value of ff.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Proof:
The idea of the proof is to find a constant such that for any nNn \in \mathbf{N}^{*}, the product of A(n)B(n)\frac{A(n)}{B(n)} and this constant is a positive integer, thereby deducing that ff is a bounded function.

First, we prove a lemma: For any non-negative real numbers x,yx, y,
[2x]+[2y][x]+[x+y][2 x]+[2 y] \geqslant[x]+[x+y]

In fact, let x=m+α,y=n+βx=m+\alpha, y=n+\beta, where m,nNm, n \in \mathbf{N}, and α,β[0,1)\alpha, \beta \in[0,1), then (2) is equivalent to proving

that is,
2m+[2α]+2n+[2β]m+(m+n)+[α+β]n+[2α]+[2β][α+β].\begin{array}{c} 2 m+[2 \alpha]+2 n+[2 \beta] \geqslant m+(m+n)+[\alpha+\beta] \\ n+[2 \alpha]+[2 \beta] \geqslant[\alpha+\beta] . \end{array}

Since [α+β]1[\alpha+\beta] \leqslant 1, and when [α+β]=1[\alpha+\beta]=1, at least one of α,β\alpha, \beta is not less than 12\frac{1}{2}, thus in this case [2α]+[2β]1[2 \alpha]+[2 \beta] \geqslant 1. Therefore, (3) holds. The lemma is proved.

Returning to the original problem, we first prove: For any nNn \in \mathbf{N}^{*}, the number (2n)!2000!n!(n+1000)!\frac{(2 n)!\cdot 2000!}{n!(n+1000)!} is a positive integer. To do this, we only need to prove that for any prime pp, the power of pp in the prime factorization of (2n)!2000!(2 n)!\cdot 2000! is not less than the power of pp in the prime factorization of n!(n+1000)!n!(n+1000)!. Using property 5, we only need to prove:
k=1+([2npk]+[2000pk])([npk]+[n+1000pk])0\sum_{k=1}^{+\infty}\left(\left[\frac{2 n}{p^{k}}\right]+\left[\frac{2000}{p^{k}}\right]\right)-\left(\left[\frac{n}{p^{k}}\right]+\left[\frac{n+1000}{p^{k}}\right]\right) \geqslant 0

If we let x=npk,y=1000pkx=\frac{n}{p^{k}}, y=\frac{1000}{p^{k}}, using (2) we know that inequality (4) holds, so (2n)!2000!n!(n+1000)!N\frac{(2 n)!\cdot 2000!}{n!(n+1000)!} \in \mathbf{N}^{*}, i.e.,
A(n)B(n)2000!N\frac{A(n)}{B(n)} \cdot 2000!\in \mathbf{N}^{*}

The above discussion shows that for any nNn \in \mathbf{N}^{*}, we have f(n)2000f(n) \mid 2000!. Noting that f(n)f(n) is 1 or a prime number, and by direct verification, 1999 is a prime number, so for any nNn \in \mathbf{N}^{*}, we have f(n)1999f(n) \leqslant 1999. Therefore, f(n)f(n) is a bounded function.

Furthermore, when n=999n=999, we know that
B(n)=1999(999!)B(n)=1999 \cdot(999!)

At this time, f(n)=1999f(n)=1999. Hence, the maximum value of f(n)f(n) is 1999.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.