Maths Olympiad Prep

Library / /352 of 520

Number theory Difficulty 6.8 National olympiad Prove it

An integer n2n \geqslant 2 having exactly ss positive divisors 1=d1<d2<<ds=n1=d_{1}<d_{2}<\cdots<d_{s}=n is said to be good if n1+d1+d2++ds1n \geqslant 1+d_{1}+d_{2}+\cdots+d_{s-1}. An integer n2n \geqslant 2 is said to be bad if it is not good.

(a) Show that there are infinitely many bad integers.

(b) Prove that, among any seven consecutive integers all greater than 2, there are always at least four good integers.

(c) Show that there are infinitely many sequences of seven consecutive good integers.

(Gerhard Woeginger, Luxembourg)

Solution

(a) Solution 1. We note that n=2mn=2^{m} has m+1m+1 divisors, dk=2k1d_{k}=2^{k-1} for 1km+11 \leqslant k \leqslant m+1. Thus

1+d1++dk1=1+(2k11)=2k1=dk 1+d_{1}+\cdots+d_{k-1}=1+\left(2^{k-1}-1\right)=2^{k-1}=d_{k}

for each k2k \geqslant 2, and hence each power of 2 is a bad integer. This exhibits infinitely many bad integers.

Remark. It is true more generally that

If n=2rmn=2^{r} m, where mm is a product of (odd) primes each less than 2r+12^{r+1}, then nn is bad.

This is an immediate corollary of the previous result and the following observation:

If n=2rmn=2^{r} m is bad, where mm is odd, then so is pnp n for any odd prime pp. Let DKD_{K} be a divisor of pnp n, so DK=pD_{K}=p or DK=dkD_{K}=d_{k} or DK=pdkD_{K}=p d_{k}, where dk>1d_{k}>1 is a divisor of nn. In the first case, observe that there exists t<r+1t<r+1 such that 2t<p<2t+12^{t}<p<2^{t+1} by assumption. Then {1,2,,2t}{D1,,DK1}\left\{1,2, \ldots, 2^{t}\right\} \subseteq\left\{D_{1}, \ldots, D_{K-1}\right\}, and so

DK=p<2t+1=1+(1+2++2t)1+D1++DK1. D_{K}=p<2^{t+1}=1+\left(1+2+\cdots+2^{t}\right) \leqslant 1+D_{1}+\cdots+D_{K-1} .

In the final case, {1,2,,2t,pd1,,pdk1}{D1,,DK1}\left\{1,2, \ldots, 2^{t}, p d_{1}, \ldots, p d_{k-1}\right\} \subseteq\left\{D_{1}, \ldots, D_{K-1}\right\}, and so

DK=pdkp(1+d1++dk1)=p+pd1++pdk<2t+1+pd1++pdk1=1+(1++2t)+pd1++pdk1<1+(D1++DK1). \begin{aligned} D_{K} & =p d_{k} \leqslant p\left(1+d_{1}+\cdots+d_{k-1}\right)=p+p d_{1}+\cdots+p d_{k} \\ & <2^{t+1}+p d_{1}+\cdots+p d_{k-1}=1+\left(1+\cdots+2^{t}\right)+p d_{1}+\cdots+p d_{k-1}<1+\left(D_{1}+\cdots+D_{K-1}\right) . \end{aligned}

In the second case, {d1,,dk1}{D1,,DK1}\left\{d_{1}, \ldots, d_{k-1}\right\} \subseteq\left\{D_{1}, \ldots, D_{K-1}\right\} immediately implies the required inequality, and so pnp n is indeed bad.

This result is weak, however: only 57931 (6.99\%) of the 829157 bad numbers not larger than 10710^{7} are of this form.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.