Maths Olympiad Prep

Track / Stage 8 / 53 of 180 #1753 of 1964

Problem 1753

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,b2a, 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 M2NM \leq 2^{N}. On the other hand M>1M>1 (and M1M-1 is a positive integer), because every neckish number is greater than 5, since for a,b2a, b \geq 2 we have: ab+b2b+b22+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 M1M-1 to M+100M+100. Then f(M1)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.