This one I took mod b-1, And then split it into even and odd cases

I got the odd case; exploga, what was your reasoning for the even case? [Also, how many points would the odd case merit?]

Sketch: Odd: pretty easy Even: some weird gap argument 2: of course I had to add this as a separate case Overall, kinda sketchy for the evens, but at least I did it.

All I did was show that for integer k greater than or equal to 1, at least k(b-1) integers cannot be made up to b^k-1+sb(b^k-1) for n=b^k-1

My solution involved splitting it into a bunch of intervals, and showing that between all the consecutive intervals, at least 1 number was skipped

Does this work?

butter67 wrote:

But what if the same term is missed for every $i?$ The regions $[2, b^i+1]$ overlap.

Cant you get any number? Because $n=(n-1)+s_{n-1}(n-1)$.

@mathtastic: $b$ is given to you; you can't choose the value of $b$ to equal $n-1.$

MSTang wrote: butter67 wrote:

But what if the same term is missed for every $i?$ The regions $[2, b^i+1]$ overlap. IDK, I submitted a different more rigorous solution on the JMO.

MSTang wrote: @mathtastic: $b$ is given to you; you can't choose the value of $b$ to equal $n-1.$ Yeah but if $n\ge 3$ then we can set b=n-1

no; $b$ is fixed, $n$ is a variable natural number

It says b is a natural number greater than or equal to 2... so we can pick our b the problem is wrong

No, you pick b first.

mathwizard888 wrote: No, you pick b first. The problem never stated that...

Someone pls tell me how good my solution is

this was how i did it: note that $s_b (n)$ is congruent to $n (mod b-1)$, so $n+ s_b (n)$ is congruent to $2n (mod b-1)$. For the odd case, $b-1$ is even so just take $odd (mod b-1$ and you can't get any of them. For the even case, we show that there are infinite number of multiples of b-1 that aren't covered. Indeed, if our integer is a multiple of $b-1$, $2n$ is congruent to $0(mod b-1)$, or $n$ is congruent to $0 (mod b-1)$. Now, just consider $n=b^k - 1$ whose representation base b is just a bunch of b-1's, and take intervals between $n= b^k -1 $ and $n = b^{k+1} - 1$

The problem statement seems really ambiguous. Usually MAA is really good about eliminating ambiguities. But it seems to imply that b is fixed, since it starts, "Let b be an integer"

For the second straight year, MAA has stolen a problem from Problems from the Book. Technically PFTB used base 10 only, but it's the same.

AkshajK wrote:

Actually, just noticed something: If $b=2$, then it's possible for $k+b^n+1$ to have a coefficient of $(b^{n+1}+1)$ if $k=b^n<b^n+1$. That kinda creates some problem for the rest of the proof.

$\phantom{}\phantom{}$

supercomputer wrote: Did anyone else get that for even $b$, you cannot get $(b-1)+a_1(b+1)+a_2(b^2+1)+\cdot\cdot\cdot$, where $0\le a_1,a_2,...\le b-1$? Wait so I've been checking with small cases and I'm pretty sure that this is true; in fact, I'm pretty sure that a number cannot be expressed as $n+s_b(n)$ if and only if it is in the above form (base 10). Could someone confirm?

My proof sketch/solution:

I guess this is similar to what tastymath750... was talking about.

For brevity let $f(n) = n + s_b(n)$. Select any integer $M$. Observe that $f(x) \ge b^{2M}$ for any $x \ge b^{2M}$, but also $f(b^{2M}-k) \ge b^{2M}$ for $k = 1, 2, \dots, M$, since the base-$b$ expansion of $b^{2M}-k$ will start out with at least $M$ digits $b-1$. Thus $f$ omits at least $M$ values in $[1, b^{2M}]$ for any $M$, as desired. $\blacksquare$ (Aside: my notes say that this problem was suggested by Palmer Mebane, who is not a PFTB author. So, likely a coincidence.)

Could someone please check the following solution? I am getting that feeling of a subtle flaw....

It looks fine to me. Two typos: 1. You want $m \in f(\mathbb N)$, not $m \in f^{-1}(\mathbb N)$, in the first line. 2. In the proof of your lemma, last line, I think you want "not bad" instead of "not good" (in the statement of the contrapositive).

Let $f(n)=n+s_b (n)$. We claim that there is at least one integer in the interval $[b^k, b^{k+1})$ that is not in the image of $f$ for each positive integer $k$. This clearly solves the problem. By the pigeonhole principle it suffices to show that there are fewer than $(b-1)b^k$ integers $n$ such that $f(n) \in [b^k, b^{k+1})$. Now the following types of integers $n$ contribute to this total. We can begin with all $n$ in the interval $[b^k, b^{k+1})$ itself, then we must add in all $n$ such that $n < b^k$ and $f(n) \ge b^k$, and then subtract all $n'$ such that $n' < b^{k+1}$ and $f(n') \ge b^{k+1}$. However, consider that for all $n$ that we add to the total, $n'=(b-1)b^k+n$ satisfies $n' < b^{k+1}$ and \[ f(n') = n' + s_b(n') = (b-1)b^k+n+(b-1)+s_b(n) \ge (b-1)b^k + b^k + (b-1) \ge b^{k+1},\]so $n'$ is an integer that we remove. To finish, we just need to show that there is another integer that we remove that is not of the aforementioned form. But if $n_0$ is the smallest integer $n_0 < b^k$ satisfying $f(n_0) \ge b^k$, then $s_b(n_0-1) \ge s_b(n_0) - 1$ since ``borrowing'' can only increase the sum of the digits of the difference when doing subtraction. Thus if we set $n_{-1}' = (b-1)b^k + n_0 - 1$, then $n_{-1}' < b^{k+1}$ and \[ f(n_{-1}') \ge (b-1)b^k + n_0 - 1 + (b-1) + s_b(n_0) - 1 \ge b^{k+1} + (b-2) \ge b^{k+1},\](since $b \ge 2$), so $n_{-1}'$ is removed from the total as well, and we are done. $\blacksquare$

Let $f(n)=n+s_b(n)$. We have $f(b^{2n}-k)\ge b^{2n}$ for all $1\le k\le n$ because the base $b$ expansion of $b^{2n}-k$ must start with at least $n$ $(b-1)'$s. We also have $f(x)\ge b^{2n}$ if $x\ge b^{2n}$. So $f$ omits at least $n$ values from $1$ to $b^{2n}$ for all $n$, as desired.

Sketch: The idea is that from $1 \leq n \leq b^k$, the maximum value of $n + s_b(n)$ is at least $b^k - 1 + (b-1)k$ which means at least $(b-1)k - 1$ values are skipped on this interval. Now we can contradict that there exist only a finite number $x$ of such integers that are not expressible as $n + s_b(n)$ by knowing that sufficiently large $k$ allows $(b-1)k - 1 > x$. Note: If $b$ is odd, then there is a very slick proof by taking modulo $b-1$ and realizing only even residues are achievable, but you do not need that to prove the statement.

mathtastic wrote: It says b is a natural number greater than or equal to 2... so we can pick our b the problem is wrong Yeah, the wording was not the greatest

Here's kind of a natural formulation to solve the problem. For $b$ odd, note that $n+s_b(n)$ is always even for mod $2 \mid b-1$ reasons, but this fact isn't too important. Lemma. [$b=2$ case] The problem holds for $b=2$. This is just simple bounding: I claim for each interval $[2^k + k, 2^{k+1} + k + 1)$, there exists a $s$ in this interval that is not expressible, thus proving the lemma. We prove this by induction on $k$, with base cases clear. Observe that we can find an $s \in [2^{k-1} + k - 1, 2^k + k)$ that is not expressible. I claim that $s + 1 + 2^k$ is not expressible too. Suppose there exists an $n$ with $n + s_2(n) = s + 2^k + 1$; then $(n-2^k) + s_2(n) = s + 1$. Note $n > 2^k$, otherwise $$n+s_2(n) < 2^k + k < s+2^k + 1.$$Now by size of $n$ we have $s_2(n-2^k) = s_2(n) - 1$, and thus $s_2(n) + n = s$; but this contradicts assumption. This completes the induction. $\blacksquare$ Now, we biject the case for general $b$ to the $b=2$ case. The idea is that every residue class mod $b-1$ is independent, so we can actually prove the following: Claim. For fixed $k$, there are infinitely many $n \equiv k \pmod {b-1}$ that are not expressible. The idea is to biject to the $b=2$ case. Notice that $n + s_b(n) \equiv 2k \pmod {b-1}$ is fixed, so we will show that there are infinitely many quotients $q = \frac{n+s_b(n)-2k}{b-1}$ that are not attainable. To complete the bijection, represent a $0$ in the base-$b$ representation of $n$ as a $0$ in base $2$, and any nonzero digit in the representation a $1$ in base $2$. Then, adding $b-1$ to $n$ is equivalent to adding $1$ to the equivalent number in base $2$; equivalently, $$s_b(n+(b-1)k) - s_b(n) = (b-1)(s_2(n+k) - s_2(n)).$$By the Lemma, infinitely many $s$ cannot be expressed as $n + s_2(n)$, so infinitely many $(b-1)s + 2k$ cannot be expressed as $n+ s_b(n)$. This completes the proof.

Consider the integers by range in each range $[2^k,2^{k+1})$. We can easily prove that there are more integers in the range with their sum with their digit sum outside the range than there are integers outside the range with their sum with their digit sum in the range. By Pigeonhole Principle, there exist integers in the range that cannot be expressed in the desired form (integer + digit sum). Since there are infinitely many ranges, there exist infinitely many desired integers. Full proof here: https://infinityintegral.substack.com/p/usajmo-2014-contest-review

Whew Define an integer $x$ to be un-$b$-earable if it cannot be expressed as $s_b(n)+n$ for some integer $n$. First, I claim that for all odd integers $b$, we have that $s_b(n)+n$ must be even. This is because by base expansion, we must have that \[n=a_0b^0+a_1b^1+\dots+a_kb^k\equiv a_0+a_1+\dots+a_k=s_b(n) \mod (b-1),\]in base $b$. This means that $s_b(n)+n\equiv 2n \mod (b-1)$. However, since $b-1$ is even, this implies that $s_b(n)+n$ must be even. This means that all odd integers are un-$b$-earable, which is infinitely many integers. This proves the problem's claim for odd $b$. Now for even integers $b$, I first claim that $2b$ is un-$b$-earable. I will do this by finding $s_b(n)+n$ for $n$ from $1$ to $2n-1$. They are as follows; 1. If $1\leq n<b$, then $s_b(n)+n=2n$, none of which can be $2b$ since $2(b-1)<2b$. 2. If $b\leq n<2b$, then $s_b(n)+n=2n-(b-1)$, which are all odd since $b$ is even, implying that none of them can be $2b$. Finally, since for all positive integers $s_b(n)\geq 1$, we have that for $n\geq 2n$; \[s_b(n)+n\geq 1+2n >2n,\]meaning that $2n$ must be un-$b$-earable. Now, I claim that if $k$ is un-$b$-earable (for even $b$) with a) the base $b$ expansion of $k$ has exactly $m-1$ (such that $m\geq 2$) digits, b) $k+b^{m-1}+1>(b^{m-1}-1)+(m-1)(b-1)$, then $k+b^{m}+1$ is also un-$b$-earable. FTSOC, assume there exists an integer $n$ such that $s_b(n)+n=k+b^{m}+1$. First, I claim that the expansion of $n$ in base $b$ must have $m$ digits, with leading digit $1$. Clearly, since $k+b^{m}+1>n$ and $k$ has $m-1$ digits in base $b$, $n$ cannot have more than $m$ digits. Therefore, FTSOC, assume that $n$ has less than $m$ digits. Then note that the max digit sum is \[b^{m-1}-1+(m-1)(b-1),\]which we have already established to be less than $k+b^{m-1}+1$, which is less than $k+b^{m}+1$, a contradiction, meaning that $n$ must have $m$ digits in base $b$. Additionally, since $k+b^{m}+1>n$, and $k$ has $m-1$ digits in base $b$, we have that the leading digit of $n$ must be $1$ in base $b$. Finally, to insure that we can continue this proof inductively for larger and larger $m$, we want to prove that \[k+b^{m-1}+1+[b^m+1]>(b^{m-1}-1)+(m-1)(b-1)+[b^m-b^{m-1}+(b-1)],\]which is always true since for all $b\geq 2$ and a positive integer $m\geq 2$, we have that \[1>b^{m-1}+(b-1),\]which proves the inequality. Finally, for the inductive step's base case, note that we already established $20_b$ is un-$b$-earable, which kickstarts our induction. This means that an infinite number of $n$ are un-$b$-earable, as desired, finishing the problem.