Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2014 USAJMO Problems/Problem 4"
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) \ge b^p</math>. If <math>b^{p+1} = S(y)</math> for some y, then <math>f(p+1) > 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) \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) > 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:00, 14 August 2014

Problem

Let $b\geq 2$ be an integer, and let $s_b(n)$ denote the sum of the digits of $n$ when it is written in base $b$. Show that there are infinitely many positive integers that cannot be represented in the form $n+s_b(n)$, where $n$ is a positive integer.

Solution

Define $S(n) = n + s_b(n)$, and call a number unrepresentable if it cannot equal $S(n)$ for a positive integer $n$. We claim that in the interval $(b^p, b^{p+1}]$ there exists an unrepresentable number, for every positive integer $p$.

If $b^{p+1}$ is unrepresentable, we're done. Otherwise, time for our lemma:

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

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

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_USAJMO_Problems/Problem_4&oldid=63069"