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 "Mock AIME 6 2006-2007 Problems/Problem 5"

(Created page with "==Problem== Let <math>S(n)</math> be the sum of the squares of the digits of <math>n</math>. How many positive integers <math>n>2007</math> satisfy the inequality <math>n-S(n...")
 
 
(41 intermediate revisions by the same user not shown)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
{{Solution}}
+
We start by rearranging the inequality the following way:
 +
 
 +
<math>n-2007\le S(n)</math> and compare the possible values for the left hand side and the right hand side of this inequality.
 +
 
 +
 
 +
'''Case 1:''' <math>n</math> has 5 digits or more.
 +
 
 +
Let <math>d</math> = number of digits of n.
 +
 
 +
Then as a function of d,
 +
 
 +
<math>10^d \le n < 10^{d+1}-1</math>, and <math>1 \le S(n) \le 9^2d</math>
 +
 
 +
<math>10^d - 2007 \le n-2007 < 10^{d+1}-2008</math>, and <math>1 \le S(n) \le 81d</math>
 +
 
 +
when <math>d \ge 5</math>,
 +
 
 +
<math>10^d - 2007 \ge 10^5 -2007</math>
 +
 
 +
<math>10^d - 2007 \ge 10^5 -2007 > 81d</math>
 +
 
 +
Since <math>10^d - 2007 > 81d</math> for <math>d \ge 5</math>, then <math>n-2007\not\le S(n)</math> and there is '''no possible <math>n</math>''' when <math>n</math> has 5 or more digits.
 +
 
 +
 
 +
'''Case 2:''' <math>n</math> has 4 digits and <math>n \ge 3000</math>
 +
 
 +
<math>3000 \le n \le 9999</math>, and <math>3^2 \le S(n) \le 3^2+3 \times 9^2</math>
 +
 
 +
<math>993 \le n-2007 \le 7992</math>, and <math>9 \le S(n) \le 252</math>
 +
 
 +
Since <math>993 > 252</math>, then <math>n-2007\not\le S(n)</math> and there is '''no possible <math>n</math>''' when <math>n</math> has 4 digits and <math>n \ge 3000</math>.
 +
 
 +
 
 +
'''Case 3:''' <math>2200 \le n \le 2999</math>
 +
 
 +
Let <math>2 \le k \le 9</math> be the 2nd digit of <math>n</math>
 +
 
 +
<math>2000+100k \le n \le 2099+100k</math>, and <math>2^2+k^2 \le S(n) \le 2^2+k^2+2 \times 9^2</math>
 +
 
 +
<math>100k-7 \le n-2007 \le 100k+92</math>, and <math>4+k^2 \le S(n) \le 166+k^2</math>
 +
 
 +
At <math>k=2</math>, <math>100k-7=193\;\;86+k^2=170</math>, <math>193>170</math>.
 +
 
 +
At <math>k=3</math>, <math>100k-7=293\;\;86+k^2=175</math>, <math>293>175</math>.
 +
 
 +
At <math>k=4</math>, <math>100k-7=393\;\;86+k^2=182</math>, <math>393>182</math>.
 +
 
 +
At <math>k=5</math>, <math>100k-7=493\;\;86+k^2=191</math>, <math>493>191</math>.
 +
 
 +
At <math>k=6</math>, <math>100k-7=593\;\;86+k^2=202</math>, <math>593>202</math>.
 +
 
 +
At <math>k=7</math>, <math>100k-7=693\;\;86+k^2=215</math>, <math>693>215</math>.
 +
 
 +
At <math>k=8</math>, <math>100k-7=793\;\;86+k^2=230</math>, <math>793>230</math>.
 +
 
 +
At <math>k=9</math>, <math>100k-7=893\;\;86+k^2=247</math>, <math>893>247</math>.
 +
 
 +
Since <math>100k-7 > 166+k^2</math>, for <math>2 \le k \le 9</math>, then <math>n-2007\not\le S(n)</math> and there is '''no possible <math>n</math>''' when <math>n \ge 2200</math> when combined with the previous cases.
 +
 
 +
 
 +
'''Case 4:''' <math>2100 \le n \le 2199</math>
 +
 
 +
Let <math>0 \le k \le 9</math> be the 3rd digit of <math>n</math>
 +
 
 +
<math>2100+10k \le n \le 2109+10k</math>, and <math>2^2+1^2+k^2 \le S(n) \le 2^2+1^2+k^2+9^2</math>
 +
 
 +
<math>10k+93 \le n-2007 \le 10k+102</math>, and <math>5+k^2 \le S(n) \le 86+k^2</math>
 +
 
 +
At <math>k=0</math>, <math>10k+93=93\;and\;86+k^2=86</math>, <math>93>86</math>.
 +
 
 +
At <math>k=1</math>, <math>10k+93=103\;and\;86+k^2=87</math>, <math>103>87</math>.
 +
 
 +
At <math>k=2</math>, <math>10k+93=113\;and\;86+k^2=90</math>, <math>113>90</math>.
 +
 
 +
At <math>k=3</math>, <math>10k+93=123\;and\;86+k^2=95</math>, <math>123>95</math>.
 +
 
 +
At <math>k=4</math>, <math>10k+93=133\;and\;86+k^2=102</math>, <math>133>102</math>.
 +
 
 +
At <math>k=5</math>, <math>10k+93=143\;and\;86+k^2=111</math>, <math>143>111</math>.
 +
 
 +
At <math>k=6</math>, <math>10k+93=153\;and\;86+k^2=122</math>, <math>153>122</math>.
 +
 
 +
At <math>k=7</math>, <math>10k+93=163\;and\;86+k^2=135</math>, <math>163>135</math>.
 +
 
 +
At <math>k=8</math>, <math>10k+93=173\;and\;86+k^2=150</math>, <math>173>150</math>.
 +
 
 +
At <math>k=9</math>, <math>10k+93=183\;and\;86+k^2=167</math>, <math>183>167</math>.
 +
 
 +
Since <math>10k+93 > 85+k^2</math>, for <math>0 \le k \le 9</math>, then <math>n-2007\not\le S(n)</math> and there is '''no possible <math>n</math>''' when <math>n \ge 2100</math> when combined with the previous cases.
 +
 
 +
From cases 1 through 4 we now know that <math>2008 \le n \le 2099</math>
 +
 
 +
'''Case 5:''' <math>2008 \le n \le 2099</math>
 +
 
 +
Let <math>a</math> and <math>b</math> be the 3rd and 4th digits of n respectively with <math>0 \le a \le 9</math> and <math>0 \le b \le 9</math>
 +
 
 +
<math>n=2000+10a+b</math>; <math>S(n)=4+a^2+b^2</math>
 +
 
 +
<math>n-2007=10a+b-7 \le S(n)=4+a^2+b^2</math>
 +
 
 +
Solving the inequality <math>10a+b-7 \le 4+a^2+b^2</math> we have:
 +
 
 +
<math>0 \le b^2-b+(a^2-10a+11)</math>
 +
 
 +
Substituting for all values of a in the above inequality we get:
 +
 
 +
When <math>a=0,\;\;0 \le b^2-b+11</math>, which gives: <math>0 \le b \le 9</math>.  But <math>n>2007</math>, So, <math>n=2008</math> and <math>n=2009</math>. Total possible <math>n</math>'s: '''2'''
 +
 
 +
When <math>a=1,\;\;0 \le b^2-b+2</math>, which gives: <math>0 \le b \le 9</math>.  Total possible <math>n</math>'s: '''10'''
 +
 
 +
When <math>a=2,\;\;0 \le b^2-b-5</math>, which gives: <math>3 \le b \le 9</math>.  Total possible <math>n</math>'s: '''7'''
 +
 
 +
When <math>a=3,\;\;0 \le b^2-b-10</math>, which gives: <math>4 \le b \le 9</math>.  Total possible <math>n</math>'s: '''6'''
 +
 
 +
When <math>a=4,\;\;0 \le b^2-b-13</math>, which gives: <math>5 \le b \le 9</math>.  Total possible <math>n</math>'s: '''5'''
 +
 
 +
When <math>a=5,\;\;0 \le b^2-b-14</math>, which gives: <math>5 \le b \le 9</math>.  Total possible <math>n</math>'s: '''5'''
 +
 
 +
When <math>a=6,\;\;0 \le b^2-b-13</math>, which gives: <math>5 \le b \le 9</math>.  Total possible <math>n</math>'s: '''5'''
 +
 
 +
When <math>a=7,\;\;0 \le b^2-b-10</math>, which gives: <math>4 \le b \le 9</math>.  Total possible <math>n</math>'s: '''6'''
 +
 
 +
When <math>a=8,\;\;0 \le b^2-b-5</math>, which gives: <math>3 \le b \le 9</math>.  Total possible <math>n</math>'s: '''7'''
 +
 
 +
When <math>a=9,\;\;0 \le b^2-b+2</math>, which gives: <math>0 \le b \le 9</math>.  Total possible <math>n</math>'s: '''10'''
 +
 
 +
Therefore, the total number of possible <math>n</math>'s is: <math>2+10+7+6+5+5+5+6+7+10=\boxed{63}</math>
 +
 
 +
~Tomas Diaz. orders@tomasdiaz.com
 +
 
 +
{{alternate solutions}}

Latest revision as of 22:02, 24 November 2023

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_6_2006-2007_Problems/Problem_5&oldid=205647"