Maths Olympiad Prep

Library / /48 of 62

Number theory Difficulty 6.5 National Olympiad Prove it Ukraine

Let us denote by deg(n)=α1+α2++αkdeg(n) = \alpha_1 + \alpha_2 + \ldots + \alpha_k the degree of the number n=p1α1p2α2pkαkn = p_1^{\alpha_1} p_2^{\alpha_2} \ldots p_k^{\alpha_k}, where pip_i are pairwise different prime numbers, and α1,α2,,αk\alpha_1, \alpha_2, \ldots, \alpha_k are positive integers. Prove that there exist 20162016 consecutive positive integers among which there are precisely 10001000 numbers with the degree less than 1111.

(Bogdan Kivva)

Solution

First let us prove the following lemma.

Lemma. There are ll consecutive positive integers, among which there are no numbers with the degree less than tt (t2t \ge 2).

Proof is conducted by Mathematical Induction with respect to tt.

Base for t=2t=2. The statement is equivalent to the fact that there are ll consecutive positive integers, none of which is prime. So it is sufficient to take (l+1)!+2,(l+1)!+3,,(l+1)!(l+1)(l+1)!+2, (l+1)!+3, \ldots, (l+1)!(l+1).

Assume that we have proved the statement for 2,3,,(t1)2, 3, \ldots, (t-1). Let us prove it for tt. Suppose for (t1)(t-1) x+1,,x+lx+1, \ldots, x+l are the numbers with the degree not less than (t1)(t-1). Now consider the numbers (x+l)!+x+1,,(x+l)!+x+l(x+l)!+x+1, \ldots, (x+l)!+x+l. Obviously, each of them has the degree not less than tt and there are ll of them. Thus, the lemma is proved.

Note that 211=2048>20162^{11} = 2048 > 2016. So among the first 20162016 positive integers all numbers have the degree less than 1111. Let w(x)w(x) be the amount of numbers with the degree less than 1111 among the numbers x+1,,x+2016x+1, \ldots, x+2016. Hence, w(0)=2016w(0) = 2016. At the same time we have shown that there are 20162016 consecutive positive integers which do not include any of the numbers with the degree less than 1111. So there exists a positive integer yy such that w(y)=0w(y)=0. It is also clear that w(z)1w(z+1)w(z)+1w(z)-1 \le w(z+1) \le w(z)+1. Thus, as w(z)w(z) takes only positive integer values or zero, in 22 consecutive points differs by not less than 11 and takes the values 00 and 20162016, it has to also take all the intermediate values, therefore 10001000 as well.

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.