Mock AIME 6 2006-2007 Problems/Problem 5

Problem

Let $S(n)$ be the sum of the squares of the digits of $n$ . How many positive integers $n>2007$ satisfy the inequality $n-S(n)\le 2007$ ?

Solution

We start by rearranging the inequality the following way:

$n-2007\le S(n)$ and compare the possible values for the left hand side and the right hand side of this inequality.

Case 1: $n$ has 5 digits or more.

Let $d$ = number of digits of n.

Then as a function of d,

$10^d \le n < 10^{d+1}-1$ , and $1 \le S(n) \le 9^2d$

$10^d - 2007 \le n-2007 < 10^{d+1}-2008$ , and $1 \le S(n) \le 81d$

when $d \ge 5$ ,

$10^d - 2007 \ge 10^5 -2007$

$10^d - 2007 \ge 10^5 -2007 > 81d$

Since $10^d - 2007 > 81d$ for $d \ge 5$ , then $n-2007\not\le S(n)$ and there is no possible $n$ when $n$ has 5 or more digits.

Case 2: $n$ has 4 digits and $n \ge 3000$

$3000 \le n \le 9999$ , and $3^2 \le S(n) \le 3^2+3 \times 9^2$

$993 \le n-2007 \le 7992$ , and $9 \le S(n) \le 252$

Since $993 > 252$ , then $n-2007\not\le S(n)$ and there is no possible $n$ when $n$ has 4 digits and $n \ge 3000$ .

Case 3: $2200 \le n \le 2999$

Let $2 \le k \le 9$ be the 2nd digit of $n$

$2000+100k \le n \le 2099+100k$ , and $2^2+k^2 \le S(n) \le 2^2+k^2+2 \times 9^2$

$100k-7 \le n-2007 \le 100k+92$ , and $4+k^2 \le S(n) \le 166+k^2$

At $k=2$ , $100k-7=193\;\;86+k^2=170$ , $193>170$ .

At $k=3$ , $100k-7=293\;\;86+k^2=175$ , $293>175$ .

At $k=4$ , $100k-7=393\;\;86+k^2=182$ , $393>182$ .

At $k=5$ , $100k-7=493\;\;86+k^2=191$ , $493>191$ .

At $k=6$ , $100k-7=593\;\;86+k^2=202$ , $593>202$ .

At $k=7$ , $100k-7=693\;\;86+k^2=215$ , $693>215$ .

At $k=8$ , $100k-7=793\;\;86+k^2=230$ , $793>230$ .

At $k=9$ , $100k-7=893\;\;86+k^2=247$ , $893>247$ .

Since $100k-7 > 166+k^2$ , for $2 \le k \le 9$ , then $n-2007\not\le S(n)$ and there is no possible $n$ when $n \ge 2200$ when combined with the previous cases.

Case 4: $2100 \le n \le 2199$

Let $0 \le k \le 9$ be the 3rd digit of $n$

$2100+10k \le n \le 2109+10k$ , and $2^2+1^2+k^2 \le S(n) \le 2^2+1^2+k^2+9^2$

$10k+93 \le n-2007 \le 10k+102$ , and $5+k^2 \le S(n) \le 86+k^2$

At $k=0$ , $10k+93=93\;and\;86+k^2=86$ , $93>86$ .

At $k=1$ , $10k+93=103\;and\;86+k^2=87$ , $103>87$ .

At $k=2$ , $10k+93=113\;and\;86+k^2=90$ , $113>90$ .

At $k=3$ , $10k+93=123\;and\;86+k^2=95$ , $123>95$ .

At $k=4$ , $10k+93=133\;and\;86+k^2=102$ , $133>102$ .

At $k=5$ , $10k+93=143\;and\;86+k^2=111$ , $143>111$ .

At $k=6$ , $10k+93=153\;and\;86+k^2=122$ , $153>122$ .

At $k=7$ , $10k+93=163\;and\;86+k^2=135$ , $163>135$ .

At $k=8$ , $10k+93=173\;and\;86+k^2=150$ , $173>150$ .

At $k=9$ , $10k+93=183\;and\;86+k^2=167$ , $183>167$ .

Since $10k+93 > 85+k^2$ , for $0 \le k \le 9$ , then $n-2007\not\le S(n)$ and there is no possible $n$ when $n \ge 2100$ when combined with the previous cases.

From cases 1 through 4 we now know that $2008 \le n \le 2099$

Case 5: $2008 \le n \le 2099$

Let $a$ and $b$ be the 3rd and 4th digits of n respectively with $0 \le a \le 9$ and $0 \le b \le 9$

$n=2000+10a+b$ ; $S(n)=4+a^2+b^2$

$n-2007=10a+b-7 \le S(n)=4+a^2+b^2$

Solving the inequality $10a+b-7 \le 4+a^2+b^2$ we have:

$0 \le b^2-b+(a^2-10a+11)$

Substituting for all values of a in the above inequality we get:

When $a=0,\;$ , $0 \le b^2-b+11$ , which gives: $0 \le b \le 9$ . But $n>2007$ , So, $n=2008$ and $n=2009$ . Total possible $n$ 's: 2

When $a=1,\;$ , $0 \le b^2-b+2$ , which gives: $0 \le b \le 9$ . Total possible $n$ 's: 10

When $a=2,\;$ , $0 \le b^2-b-5$ , which gives: $3 \le b \le 9$ . Total possible $n$ 's: 7

When $a=3,\;$ , $0 \le b^2-b-10$ , which gives: $4 \le b \le 9$ . Total possible $n$ 's: 6

When $a=4,\;$ , $0 \le b^2-b-13$ , which gives: $5 \le b \le 9$ . Total possible $n$ 's: 5

When $a=5,\;$ , $0 \le b^2-b-14$ , which gives: $5 \le b \le 9$ . Total possible $n$ 's: 5

When $a=6,\;$ , $0 \le b^2-b-13$ , which gives: $5 \le b \le 9$ . Total possible $n$ 's: 5

When $a=7,\;$ , $0 \le b^2-b-10$ , which gives: $4 \le b \le 9$ . Total possible $n$ 's: 6

When $a=8,\;$ , $0 \le b^2-b-5$ , which gives: $3 \le b \le 9$ . Total possible $n$ 's: 7

When $a=9,\;$ , $0 \le b^2-b+2$ , which gives: $0 \le b \le 9$ . Total possible $n$ 's: 10

Therefore, the total number of possible $n$ 's is: $2+10+7+6+5+5+5+6+7+10=\boxed{63}$

~Tomas Diaz. orders@tomasdiaz.com

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Page

Toolbox

Search

Mock AIME 6 2006-2007 Problems/Problem 5

Problem

Solution