Maths Olympiad Prep

Library / /3 of 19

Number theory Difficulty 7.7 National Olympiad, round 2 Prove it Estonia

For every positive integer xx, denote by κ(x)\kappa(x) the number of composite numbers not greater than xx. Find all positive integers nn such that
(κ(n))!lcm(1,2,,n)>(n1)! (\kappa(n))! \cdot \text{lcm}(1,2,\dots,n) > (n-1)!

Solution

The inequality holds for n=2,3,4,5,7,9n = 2,3,4,5,7,9 and does not hold for n=1,6,8,10,11,12n = 1,6,8,10,11,12. Assume in the rest that n13n \ge 13. By definition of κ(n)\kappa(n), there exists exactly n1κ(n)n-1-\kappa(n) prime numbers not greater than nn; these are the primes dividing lcm(1,2,,n)\text{lcm}(1,2,\dots,n). We have n1κ(n)6n-1-\kappa(n) \ge 6 as n13n \ge 13. Let q1,,qn1κ(n)q_1, \dots, q_{n-1-\kappa(n)} be all prime powers in the canonical representation of lcm(1,2,,n)\text{lcm}(1,2,\dots,n). W.l.o.g., q1>q2>>qn1κ(n)q_1 > q_2 > \dots > q_{n-1-\kappa(n)}. As at least 5 numbers among q1,,q6q_1, \dots, q_6 are odd, in the case of odd nn we have q1q2q3q4q5q6n(n1)(n2)(n4)(n6)(n8)q_1q_2q_3q_4q_5q_6 \le n(n-1)(n-2)(n-4)(n-6)(n-8) and in the case of even nn similarly q1q2q3q4q5q6n(n1)(n3)(n5)(n7)(n9)q_1q_2q_3q_4q_5q_6 \le n(n-1)(n-3)(n-5)(n-7)(n-9). But since (n3)(n5)(n7)(n9)<(n2)(n4)(n6)(n8)(n-3)(n-5)(n-7)(n-9) < (n-2)(n-4)(n-6)(n-8) and n(n8)<(n3)(n5)n(n-8) < (n-3)(n-5), we anyway obtain
q1q2q3q4q5q6<(n1)(n2)(n3)(n4)(n5)(n6)=(n1)!(n7)! q_1q_2q_3q_4q_5q_6 < (n-1)(n-2)(n-3)(n-4)(n-5)(n-6) = \frac{(n-1)!}{(n-7)!}
As q6<n6q_6 < n-6, the inequality qi<niq_i < n-i holds for every i>6i > 6, whence
q7qn1κ(n)(n7)(κ(n)+1)=(n7)!(κ(n))! q_7 \cdots q_{n-1-\kappa(n)} \le (n-7) \cdots (\kappa(n)+1) = \frac{(n-7)!}{(\kappa(n))!}
Consequently, lcm(1,2,,n)=q1q2qn1κ(n)<(n1)!(κ(n))!\text{lcm}(1,2,\dots,n) = q_1q_2\cdots q_{n-1-\kappa(n)} < \frac{(n-1)!}{(\kappa(n))!}, contradicting the original inequality. Hence the inequality holds for n=2,3,4,5,7,9n = 2,3,4,5,7,9 only.

Want a route through all this instead of 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 reproduced verbatim; metadata (topic, difficulty) added by this project.