Difference between revisions of "2014 USAJMO Problems/Problem 4"
(→Solution) |
(→Solution) |
||
Line 9: | Line 9: | ||
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) > b^p</math>. If <math>b^{p+1} = S(x)</math> for some x, then <math>f(p+1) \ge f(p)</math>. | 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) > b^p</math>. If <math>b^{p+1} = S(x)</math> for some x, then <math>f(p+1) \ge 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) > 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>x > b * b^p</math>. Removing the digit <math>(b-1)</math> from the front of x creates a number that is not in <math>F(p)</math>. Hence, <math>F(p) \ | + | Proof: Let <math>F(p)</math> be the set of integers x less than <math>b^p</math> such that <math>S(x) > 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>x > b * b^p</math>. Removing the digit <math>(b-1)</math> from the front of x 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 19:38, 30 April 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 x, 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 x 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.