Maths Olympiad Prep

Track / Stage 6 / 28 of 400 #1028 of 1964

Problem 1028

National Olympiad, first round
Number theory Difficulty 6.0 Prove it Serbian Mathematical Olympiad · Serbia

For a natural number nn we say that it is quirky if and only if there exist natural numbers a>1a>1 and b>1b>1 such that n=ab+bn=a^{b}+b. Does there exist 2014 consecutive natural numbers among which exactly 2012 are quirky numbers?

(Miloš Milosavljević)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

We will first give an example of 2012 consecutive quirky numbers. It suffices to take the numbers N+2,N+3,,N+2013N+2, N+3, \ldots, N+2013, where N=22013!N=2^{2013!}.
For a natural number nn, let us denote by f(n)f(n) the number of quirky numbers among n,n+1,,n+2013n, n+1, \ldots, n+2013. Since f(1)<2012f(1)<2012 (the numbers 1,2,3,4,51,2,3,4,5 are not quirky), f(N)2012f(N) \geqslant 2012 and f(n+1)f(n)1|f(n+1)-f(n)| \leqslant 1 for every nn, there exists nn such that f(n)=2012f(n)=2012.

Second solution. Let us denote N=2014!2011N=\frac{2014!}{2011}. The numbers 2N+i2^{N}+i for 2i20102 \leqslant i \leqslant 2010 and 2012i20142012 \leqslant i \leqslant 2014 are quirky; let us prove that 2N+12^{N}+1 and 2N+20112^{N}+2011 are not.
Suppose that 2N+2011=ab+b2^{N}+2011=a^{b}+b (the number 2N+12^{N}+1 is examined similarly). From 2bab<2N2^{b} \leqslant a^{b}<2^{N} it follows that b<Nb<N. Also b>2011b>2011, since otherwise we would have 2011b=ab2N=(a2Nb)(+2(b1)Nb)>2Nb>20112011-b=a^{b}-2^{N}=\left(a-2^{\frac{N}{b}}\right)\left(\cdots+2^{\frac{(b-1) N}{b}}\right)>2^{\frac{N}{b}}>2011. Further, if 2a2 \mid a, we have 2b2Nab=b2011<2b2^{b} \mid 2^{N}-a^{b}=b-2011<2^{b}, which is impossible. Finally, for 2a2 \nmid a and 2b2 \mid b we have b2011=(2N2ab2)(2N2+ab2)>2N2b-2011=\left(2^{\frac{N}{2}}-a^{\frac{b}{2}}\right)\left(2^{\frac{N}{2}}+a^{\frac{b}{2}}\right)>2^{\frac{N}{2}}, so 2N+2011=ab+b>22N/22^{N}+2011=a^{b}+b>2^{2^{N / 2}}, again impossible since 2N2>N2^{\frac{N}{2}}>N.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from sr; metadata (topic, difficulty, ordering) added by this project.