Maths Olympiad Prep

Track / Stage 8 / 23 of 180 #2363 of 2604

Problem 2363

IMO Shortlist mid-range; USAMO P2/P5
Number theory Difficulty 8.1 Prove it Auswahlklausur / · Germany · 2014

A positive integer nn is called neckish if it can be written in the form n=ab+bn = a^{b} + b with two integers a,b≥2a, b \geq 2.
Decide whether there exist 102 consecutive positive integers, of which exactly 100 are neckish.

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

Solution:

Such numbers exist. For a positive integer mm let f(m)f(m) be the number of neckish numbers among the 102 consecutive numbers m,m+1,m+2,…,m+101m, m+1, m+2, \ldots, m+101. Let NN be the least common multiple of the numbers 2,3,4,…,1012,3,4, \ldots, 101. Then f(2N)≥100f\left(2^{N}\right) \geq 100, since for all b=2,3,…,101b=2,3, \ldots, 101 we have: 2N+b=(2N/b)b+b2^{N}+b=\left(2^{N / b}\right)^{b}+b is neckish. Thus there is also a smallest positive number MM with f(M)≥100f(M) \geq 100. Clearly M≤2NM \leq 2^{N}. On the other hand M>1M>1 (and M−1M-1 is a positive integer), because every neckish number is greater than 5, since for a,b≥2a, b \geq 2 we have: ab+b≥2b+b≥22+2=6a^{b}+b \geq 2^{b}+b \geq 2^{2}+2=6, and thus among the numbers from 1 to 102 at most 97 are neckish. Now it is shown that f(M)=100f(M)=100: If f(M)>100f(M)>100 held, there would be among the numbers from MM to M+101M+101 at least 101 neckish ones, hence among those from MM to M+100M+100 at least 100 neckish ones, and likewise among those from M−1M-1 to M+100M+100. Then f(M−1)≥100f(M-1) \geq 100 would hold, contradicting the minimality of MM. Therefore f(M)=100f(M)=100. The numbers from MM to M+101M+101 thus satisfy the condition.

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