Maths Olympiad Prep

Track / Stage 6 / 43 of 400 #1683 of 2604

Problem 1683

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 2⩽i⩽20102 \leqslant i \leqslant 2010 and 2012⩽i⩽20142012 \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 2b⩽ab<2N2^{b} \leqslant a^{b}<2^{N} it follows that b<Nb<N. Also b>2011b>2011, since otherwise we would have 2011−b=ab−2N=(a−2Nb)(⋯+2(b−1)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 2∣a2 \mid a, we have 2b∣2N−ab=b−2011<2b2^{b} \mid 2^{N}-a^{b}=b-2011<2^{b}, which is impossible. Finally, for 2∤a2 \nmid a and 2∣b2 \mid b we have b−2011=(2N2−ab2)(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.