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: |
Revision as of 13:29, 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.