Difference between revisions of "2014 USAJMO Problems/Problem 4"
(Created page with "==Problem== Let <math>b\geq 2</math> be an integer, and let <math>s_b(n)</math> denote the sum of the digits of <math>n</math> when it is written in base <math>b</math>. Show th...") |
(→Solution) |
||
| Line 2: | Line 2: | ||
Let <math>b\geq 2</math> be an integer, and let <math>s_b(n)</math> denote the sum of the digits of <math>n</math> when it is written in base <math>b</math>. Show that there are infinitely many positive integers that cannot be represented in the form <math>n+s_b(n)</math>, where <math>n</math> is a positive integer. | Let <math>b\geq 2</math> be an integer, and let <math>s_b(n)</math> denote the sum of the digits of <math>n</math> when it is written in base <math>b</math>. Show that there are infinitely many positive integers that cannot be represented in the form <math>n+s_b(n)</math>, where <math>n</math> is a positive integer. | ||
==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>. | ||
| + | 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</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) > 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) -> 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. | ||
Revision as of 17:06, 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.
