Olympiad Maths Prep

Library / /5 of 6

Number theory Difficulty 7.0 National olympiad, round 2 Prove it Argentina

Consider the product Pn=1!2!3!n!P_n = 1! \cdot 2! \cdot 3! \cdot \dots \cdot n!, where n!=123nn! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n, for every positive integer nn.

a) Find all possible values of positive integers mm such that P2020m!\frac{P_{2020}}{m!} is a perfect square.

b) Prove that there exist infinitely many values of nn such that Pnm!\frac{P_n}{m!} is a perfect square for at least two positive integers mm.

Solution

a) First, note that
P2020=1(12)(123)(1232020)=120202201932018201922020=(11010210093100920182019)2(2462020)=(11010210093100920182019)2210101010! \begin{aligned} P_{2020} &= 1 \cdot (1 \cdot 2) \cdot (1 \cdot 2 \cdot 3) \cdots (1 \cdot 2 \cdot 3 \cdots 2020) = 1^{2020} \cdot 2^{2019} \cdot 3^{2018} \cdots 2019^2 \cdot 2020 \\ &= (1^{1010} \cdot 2^{1009} \cdot 3^{1009} \cdots 2018 \cdot 2019)^2 \cdot (2 \cdot 4 \cdot 6 \cdots 2020) \\ &= (1^{1010} \cdot 2^{1009} \cdot 3^{1009} \cdots 2018 \cdot 2019)^2 \cdot 2^{1010} \cdot 1010! \end{aligned}
which implies that m=1010m = 1010 is a solution.

Assume there is another solution mm. Then, as P2020/1010!P_{2020}/1010! is a perfect square, we have that
P2020/m!P2020/1010!=1010!m! \frac{P_{2020}/m!}{P_{2020}/1010!} = \frac{1010!}{m!}
is the square of a rational number.

If m<1009m < 1009, then 1010!/m!1010!/m! is an integer that is a multiple of 10091009, which is prime, but not a multiple of 100921009^2; therefore, mm is not a solution. It is clear that m=1009m = 1009 is not a solution either.

If m1013m \ge 1013, then m!/1010!m!/1010! is a multiple of 10131013, which is prime; so, in order that it is a multiple of 101321013^2, we should have m21013=2026m \ge 2 \cdot 1013 = 2026. But 20272027 is prime and P2020P_{2020} does not have 20272027 as a factor; then m<2027m < 2027. Thus, the only possibility is m=2026m = 2026, which is not a solution, since 2026!/1010!2026!/1010! is a multiple of 10191019, which is prime, but not a multiple of 101921019^2.

The remaining cases are m=1011m = 1011 and m=1012m = 1012. It is immediate to verify that they are not solutions, since 10111011 and 101110121011 \cdot 1012 are not perfect squares.

b) Similarly as in a), note that if n=4tn = 4t and m=2tm = 2t for a positive integer tt, then Pn/m!P_n/m! is a perfect square, since
Pn=14t24t134t2(4t1)24t=(12t22t132t1(4t1))222t(2t)! P_n = 1^{4t} \cdot 2^{4t-1} \cdot 3^{4t-2} \cdots (4t-1)^2 \cdot 4t = (1^{2t} \cdot 2^{2t-1} \cdot 3^{2t-1} \cdots (4t-1))^2 \cdot 2^{2t} \cdot (2t)!

Consider n=8(k2+k)n = 8(k^2 + k). Then, as we have already shown, for m=4(k2+k)m = 4(k^2 + k) we have a solution. We will now show that Pn/(m+1)!P_n/(m+1)! is also a perfect square. Note that m+1=4k2+4k+1=(2k+1)2m+1 = 4k^2 + 4k + 1 = (2k+1)^2, and
Pn(m+1)!=1m+1Pnm!=1(2k+1)2(1m2m1(2k+1)mk(n1))22m=(1m2m1(2k+1)mk1(n1))22m \begin{aligned} \frac{P_n}{(m+1)!} &= \frac{1}{m+1} \cdot \frac{P_n}{m!} = \frac{1}{(2k+1)^2} \cdot (1^m \cdot 2^{m-1} \cdots (2k+1)^{m-k} \cdots (n-1))^2 \cdot 2^m \\ &= (1^m \cdot 2^{m-1} \cdots (2k+1)^{m-k-1} \cdots (n-1))^2 \cdot 2^m \end{aligned}
which is an integer, since mk1=4k2+3k1>0m-k-1 = 4k^2 + 3k - 1 > 0 for k1k \ge 1.

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.