# Difference between revisions of "2014 USAJMO Problems/Problem 4"

Mathcool2009 (talk | contribs) |
Mathcool2009 (talk | contribs) |
||

Line 3: | Line 3: | ||

==Solution== | ==Solution== | ||

Define <math>S(n) = n + s_b(n)</math>, and call a number ''unrepresentable'' if it cannot equal <math>S(n)</math> for a positive integer <math>n</math>. | Define <math>S(n) = n + s_b(n)</math>, and call a number ''unrepresentable'' if it cannot equal <math>S(n)</math> for a positive integer <math>n</math>. | ||

− | We claim that in the interval <math> | + | We claim that in the interval <math>(b^p, b^{p+1}]</math> there exists an unrepresentable number, for every positive integer <math>p</math>. |

If <math>b^{p+1}</math> is unrepresentable, we're done. Otherwise, time for our lemma: | If <math>b^{p+1}</math> is unrepresentable, we're done. Otherwise, time for our lemma: | ||

− | Lemma: Define the function <math>f(p)</math> to equal the number of integer x less than <math>b^p</math> such that <math>S(x) | + | Lemma: Define the function <math>f(p)</math> to equal the number of integer x less than <math>b^p</math> such that <math>S(x) \ge b^p</math>. If <math>b^{p+1} = S(y)</math> for some y, then <math>f(p+1) > f(p)</math>. |

Proof: Let <math>F(p)</math> be the set of integers x less than <math>b^p</math> such that <math>S(x) \ge b^p</math>. Then for every integer in <math>F(p)</math>, append the digit <math>(b-1)</math> to the front of it to create a valid integer in <math>F(p+1)</math>. Also, notice that <math>(b-1) \cdot b^p \le y < b^{p+1}</math>. Removing the digit <math>(b-1)</math> from the front of y creates a number that is not in <math>F(p)</math>. Hence, <math>F(p) \rightarrow F(p+1)</math>, but there exists an element of <math>F(p+1)</math> not corresponding with <math>F(p)</math>, so <math>f(p+1) > f(p)</math>. | Proof: Let <math>F(p)</math> be the set of integers x less than <math>b^p</math> such that <math>S(x) \ge b^p</math>. Then for every integer in <math>F(p)</math>, append the digit <math>(b-1)</math> to the front of it to create a valid integer in <math>F(p+1)</math>. Also, notice that <math>(b-1) \cdot b^p \le y < b^{p+1}</math>. Removing the digit <math>(b-1)</math> from the front of y creates a number that is not in <math>F(p)</math>. Hence, <math>F(p) \rightarrow F(p+1)</math>, but there exists an element of <math>F(p+1)</math> not corresponding with <math>F(p)</math>, so <math>f(p+1) > f(p)</math>. | ||

Note that our lemma combined with the Pigeonhole Principle essentially proves the claim. Therefore, because there are infinitely many intervals containing an unrepresentable number, there are infinitely many unrepresentable numbers. | Note that our lemma combined with the Pigeonhole Principle essentially proves the claim. Therefore, because there are infinitely many intervals containing an unrepresentable number, there are infinitely many unrepresentable numbers. |

## Revision as of 16:33, 14 August 2014

## Problem

Let be an integer, and let denote the sum of the digits of when it is written in base . Show that there are infinitely many positive integers that cannot be represented in the form , where is a positive integer.

## Solution

Define , and call a number *unrepresentable* if it cannot equal for a positive integer .
We claim that in the interval there exists an unrepresentable number, for every positive integer .

If is unrepresentable, we're done. Otherwise, time for our lemma:

Lemma: Define the function to equal the number of integer x less than such that . If for some y, then .

Proof: Let be the set of integers x less than such that . Then for every integer in , append the digit to the front of it to create a valid integer in . Also, notice that . Removing the digit from the front of y creates a number that is not in . Hence, , but there exists an element of not corresponding with , so .

Note that our lemma combined with the Pigeonhole Principle essentially proves the claim. Therefore, because there are infinitely many intervals containing an unrepresentable number, there are infinitely many unrepresentable numbers.