Problem:
Let b≥2 be an integer, and let sb​(n) denote the sum of the digits of n when it is written in base b. Show that there are infinitely many positive integers that cannot be represented in the form n+sb​(n), where n is a positive integer.
Solution:
Let f(n)=n+sb​(n). For a positive integer m, let k=⌊logb​(m/2)⌋, so that m≥2bk. Note that if bm−bk≤n<bm, then the base b expansion of n begins with m−k digits equal to b−1, and therefore
f(n)>bm−bk+(m−k)(b−1)≥bm−bk+(2bk−k)(b−1)≥bm(1)
Now consider the set {f(1),f(2),…,f(bm)}. Any number that is ≤bm and in the range of f is in this set. However, we see from (1) that f(n)>bm whenever bm−bk≤n<bm. Therefore, there are at least bk numbers from 1 to bm that are not in the range of f. Since k goes to infinity as m goes to infinity, the desired result follows.
This problem and solution was suggested by Palmer Mebane.
OR
We first show that there exist infinitely many pairs (n1​,m1​),(n2​,m2​),… such that ni​+sb​(ni​)=mi​+sb​(mi​) for all i.
- Case 1b=2. Let i be a positive integer, and set j=2i+3; note j>i. Then for ni​=2j−1, we have s2​(ni​)=j. If we then consider mi​=2j+j−3, we have by the definition of j that mx​=2j+2i, so s2​(mi​)=2. It is easy to see that ni​+s2​(ni​)=mi​+s2​(mi​).
- Case 2b>2. Let i be a positive integer, and set j=b−1bi+b−2​+1; note j>i. Then for ni​=bj−b+2, we have sb​(ni​)=(b−1)(j−1)+2. If we then consider mi​=bj−b+(b−1)(j−1)+2, plugging in our definition for j in the third term gives
mi​=bj−b+(b−1)(b−1bi+b−2​)+2=bj+bi
so sb​(mi​)=2. We can easily compute that ni​+sb​(ni​)=mi​+sb​(mi​).
In both cases, since j grows exponentially with i, it is easy to check that ni​<mi​< ni+1​<mi+1​, so all of the constructed pairs contain pairwise distinct positive integers.
Now we will show at least k positive integers cannot be represented in the form n+sb​(n) for any k. Take (n1​,m1​),…(nk​,mk​) and let A be a number greater than any of the 2k numbers in these pairs. For a positive integer x with x≤A, if we have x=n+sb​(n) then we must have n≤x≤A. So in finding ways to represent the numbers 1,2,…A in the form n+sb​(n), all of them require n≤A. However, among numbers at most A there are at least k pairs ni​,mi​ with ni​+sb​(ni​)=mi​+sb​(mi​). Therefore the set {n+sb​(n)∣n=1,2,...A} has at most A−k elements, and so at least k of the numbers 1,2,…A are not members of this set and thus have no representation in the form n+sb​(n). This proves our original claim. Since k is arbitrary there cannot be a finite amount of positive integers with no representation, so there are infinitely many as desired.
The second solution was suggested by Palmer Mebane.
The problems on this page are the property of the MAA's American Mathematics Competitions