Maths Olympiad Prep

Library / /67 of 94

Number theory Difficulty 6.6 National Olympiad Prove it Hong Kong

For each positive integer nn larger than 11 with prime factorization p1α1p2α2pkαkp_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}, its signature is defined as the sum α1+α2++αk\alpha_1 + \alpha_2 + \cdots + \alpha_k. Does there exist 20202020 consecutive positive integers such that among them, there are exactly 18121812 integers whose signatures are strictly smaller than 1111?

Solution

Yes. Let f(n)f(n) be the number of integers among n+1,n+2,,n+2020n+1, n+2, \dots, n+2020 having signatures less than 1111. Since 211=2048>20212^{11} = 2048 > 2021, all of 2,3,,20212, 3, \dots, 2021 have signatures smaller than 1111. Therefore, we have f(1)=2020f(1) = 2020.

Next, let p1,p2,,p2020p_1, p_2, \dots, p_{2020} be distinct primes. By the Chinese remainder theorem,

there exists a positive integer mm such that
l@ l@ l m -1 p 1 11 , m -2 p 2 11 , m -2020 p 2020 11 .\text{l@ l@ l m -1 p 1 11 , m -2 p 2 11 , m -2020 p 2020 11 .}
For this mm, since pj11p_j^{11} divides m+jm+j for j=1,2,,2020j = 1, 2, \dots, 2020, each of the integers m+1,m+2,,m+2020m+1, m+2, \dots, m+2020 has signature larger than or equal to 1111. This implies f(m)=0f(m) = 0.

Now, when we move from the integers n+1,n+2,,n+2020n+1, n+2, \dots, n+2020 to the integers n+2,n+3,,n+2021n+2, n+3, \dots, n+2021, the number of integers with signature less than 1111 will be increased or decreased by 11, or remain unchanged. Thus, the difference between f(n)f(n) and f(n+1)f(n+1) is at most 11. Therefore, in order to decrease f(1)=2020f(1) = 2020 to f(m)=0f(m) = 0, we must come across a positive integer kk such that f(k)=1812f(k) = 1812, and we are done.

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.