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 "2003 AMC 10A Problems/Problem 25"

(Alternate solution)
m
 
(38 intermediate revisions by 23 users not shown)
Line 4: Line 4:
 
<math> \mathrm{(A) \ } 8180\qquad \mathrm{(B) \ } 8181\qquad \mathrm{(C) \ } 8182\qquad \mathrm{(D) \ } 9000\qquad \mathrm{(E) \ } 9090 </math>
 
<math> \mathrm{(A) \ } 8180\qquad \mathrm{(B) \ } 8181\qquad \mathrm{(C) \ } 8182\qquad \mathrm{(D) \ } 9000\qquad \mathrm{(E) \ } 9090 </math>
  
−
== Solution ==
+
== Solutions ==
 +
=== Simple Solution ===
 +
<math>11|(q+r)</math> implies that <math>11|(99q+q+r)</math> and therefore <math>11|(100q+r)</math>, so <math>11|n</math>. Then, <math>n</math> can range from <math>10010</math> to <math>99990</math> for a total of <math>\boxed{8181\Rightarrow \mathrm{(B)}}</math> numbers.
 +
 
 +
<3
 +
 
 
=== Solution 1 ===
 
=== Solution 1 ===
 
When a <math>5</math>-digit number is divided by <math>100</math>, the first <math>3</math> digits become the quotient, <math>q</math>, and the last <math>2</math> digits become the remainder, <math>r</math>.  
 
When a <math>5</math>-digit number is divided by <math>100</math>, the first <math>3</math> digits become the quotient, <math>q</math>, and the last <math>2</math> digits become the remainder, <math>r</math>.  
Line 10: Line 15:
 
Therefore, <math>q</math> can be any integer from <math>100</math> to <math>999</math> inclusive, and <math>r</math> can be any integer from <math>0</math> to <math>99</math> inclusive.  
 
Therefore, <math>q</math> can be any integer from <math>100</math> to <math>999</math> inclusive, and <math>r</math> can be any integer from <math>0</math> to <math>99</math> inclusive.  
  
−
For each of the <math>9\cdot10\cdot10=900</math> possible values of <math>q</math>, there are at least <math>\lfloor \frac{100}{11} \rfloor = 9</math> possible values of <math>r</math> such that <math>q+r \equiv 0\pmod{11}</math>.  
+
For each of the <math>9\cdot10\cdot10=900</math> possible values of <math>q</math>, there are at least <math>\left\lfloor \frac{100}{11} \right\rfloor = 9</math> possible values of <math>r</math> such that <math>q+r \equiv 0\pmod{11}</math>.  
 +
 
 +
Since there is <math>1</math> "extra" possible value of <math>r</math> that is congruent to <math>0\pmod{11}</math>, each of the <math>\left\lfloor \frac{900}{11} \right\rfloor = 81</math> values of <math>q</math> that are congruent to <math>0\pmod{11}</math> have <math>1</math> more possible value of <math>r</math> such that <math>q+r \equiv 0\pmod{11}</math>. Another way to think about it is the number of possible values of q when r, the remainder, is <math>0</math>. In this case, q itself has to be a multiple of <math>11</math>. <math>\left\lfloor \frac{999}{11} = 90 \right\rfloor</math>. Then we'll need to subtract <math>9</math> from <math>90</math> since we only want multiples of <math>11</math> greater than <math>100</math> <math>(90-9=81)</math>
  
−
Since there is <math>1</math> "extra" possible value of <math>r</math> that is congruent to <math>0\pmod{11}</math>, each of the <math>\lfloor \frac{900}{11} \rfloor = 81</math> values of <math>q</math> that are congruent to <math>0\pmod{11}</math> have <math>1</math> more possible value of <math>r</math> such that <math>q+r \equiv 0\pmod{11}</math>.  
+
Therefore, the number of possible values of <math>n</math> such that <math>q+r \equiv 0\pmod{11}</math> is <math>900\cdot9+81\cdot1=8181 \Rightarrow B</math>.
  
−
Therefore, the number of possible values of <math>n</math> such that <math>q+r \equiv 0\pmod{11}</math> is <math>900\cdot9+81\cdot1=8181 \Rightarrow B</math>.
+
~ Minor Edit by PlainOldNumberTheory
  
 
=== Solution 2 ===
 
=== Solution 2 ===
−
Let <math>n</math> equal <math>\underline{abcde}</math>, where <math>a</math> through <math>e</math> are digits. Therefore,
+
Let <math>n</math> equal <math>\overline{abcde}</math>, where <math>a</math> through <math>e</math> are digits. Therefore,
  
−
<math>q=\underline{abc}=100a+10b+c</math>
+
<math>q=\overline{abc}=100a+10b+c</math>
  
−
<math>r=\underline{de}=10d+e</math>
+
<math>r=\overline{de}=10d+e</math>
  
 
We now take <math>q+r\bmod{11}</math>:
 
We now take <math>q+r\bmod{11}</math>:
Line 29: Line 36:
 
The divisor trick for 11 is as follows:
 
The divisor trick for 11 is as follows:
  
−
"Let <math>n=\underline{a_1a_2a_3\cdots a_x}</math> be an <math>x</math> digit integer. If <math>a_1-a_2+a_3-\cdots +(-1)^{x-1} a_x</math> is divisible by <math>11</math>, then <math>n</math> is also divisible by 11."
+
"Let <math>n=\overline{a_1a_2a_3\cdots a_x}</math> be an <math>x</math> digit integer. If <math>a_1-a_2+a_3-\cdots +(-1)^{x-1} a_x</math> is divisible by <math>11</math>, then <math>n</math> is also divisible by <math>11</math>."
 +
 
 +
Therefore, the five-digit number <math>n</math> is divisible by 11. The 5-digit multiples of 11 range from <math>910\cdot 11</math> to <math>9090\cdot 11</math>. There are <math>8181\Rightarrow \mathrm{(B)}</math> divisors of 11 between those inclusive.
 +
 
 +
==== Note ====
 +
 
 +
The part labeled "divisor trick" actually follows from the same observation we made in the previous step: <math>10\equiv (-1)\pmod{11}</math>, therefore <math>10^{2k}\equiv 1</math> and <math>10^{2k+1}\equiv (-1)</math> for all <math>k</math>.  
 +
For a <math>5-</math>digit number <math>\overline{abcde}</math> we get <math>\overline{abcde}\equiv a\cdot 1 + b\cdot(-1) + c\cdot 1 + d\cdot(-1) + e\cdot 1 = a-b+c-d+e</math>, as claimed.
 +
 
 +
Also note that in the "divisor trick" we want to assign the signs backward - if we make sure that the last sign is a <math>+</math>, the result will have the same remainder modulo <math>11</math> as the original number.
  
−
Therefore, the five digit number <math>n</math> is divisible by 11. The 5-digit multiples of 11 range from <math>910\cdot 11</math> to <math>9090\cdot 11</math>. There are <math>8181\Rightarrow \mathrm{(B)}</math> divisors of 11 between those inclusive.
+
=== Solution 3 ===
 +
 
 +
Since <math>q</math> is a quotient and <math>r</math> is a remainder when <math>n</math> is divided by <math>100</math>. So we have <math>n=100q+r</math>. Since we are counting choices where <math>q+r</math> is divisible by <math>11</math>, we have <math>n=99q+q+r=99q+11k</math> for some <math>k</math>. This means that <math>n</math> is the sum of two multiples of <math>11</math> and would thus itself be a multiple of <math>11</math>. Then we can count all the five-digit multiples of <math>11</math> as in Solution 2. (This solution is essentially the same as Solution 2, but it does not necessarily involve mods and so could potentially be faster.)
 +
 
 +
=== Solution 4 ===
 +
 
 +
Defining <math>q</math> and <math>r</math> in terms of floor functions and <math>n</math> would yield: <math>q=\left \lfloor \frac{n}{100} \right \rfloor</math> and <math>r=n-100 \left \lfloor \frac{n}{100} \right \rfloor</math>. Since <math>q+r \equiv 0\pmod{11}</math>, <math>\left \lfloor \frac{n}{100} \right \rfloor + n-100 \left \lfloor \frac{n}{100} \right \rfloor \equiv 0\pmod{11}</math>. Simplifying gets us <math>n-99 \left \lfloor \frac{n}{100} \right \rfloor\equiv 0\pmod{11} \rightarrow n \equiv 0\pmod{11}</math> (<math>99 \left \lfloor \frac{n}{100} \right \rfloor\equiv 0\pmod{11}</math> is always true since floor function always yields an integer, and 99 is divisible by 11 w/o any remainder). After we come to this conclusion, it becomes easy to solve the rest of the problem (<math>\left \lfloor \frac{n}{99999} \right \rfloor - \left \lfloor \frac{n}{10000} \right \rfloor</math>).
 +
~hw21
 +
 
 +
==Video Solution 1==
 +
https://youtu.be/OpGHj-B0_hg?t=672
 +
 
 +
~IceMatrix
 +
 
 +
==Video Solution 2==
 +
https://youtu.be/j5iM4V7ZT-Y
 +
 
 +
~savannahsolver
  
 
== See Also ==
 
== See Also ==
−
{{AMC10 box|year=2003|ab=A|num-b=24|after=Final Question}}
+
{{AMC10 box|year=2003|ab=A|num-b=24|after=Last Question}}
−
 
+
{{AMC12 box|year=2003|ab=A|num-b=17|num-a=19}}
 
[[Category:Introductory Number Theory Problems]]
 
[[Category:Introductory Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 19:57, 29 May 2023

Problem

Let $n$ be a $5$-digit number, and let $q$ and $r$ be the quotient and the remainder, respectively, when $n$ is divided by $100$. For how many values of $n$ is $q+r$ divisible by $11$?

$\mathrm{(A) \ } 8180\qquad \mathrm{(B) \ } 8181\qquad \mathrm{(C) \ } 8182\qquad \mathrm{(D) \ } 9000\qquad \mathrm{(E) \ } 9090$

Solutions

Simple Solution

$11|(q+r)$ implies that $11|(99q+q+r)$ and therefore $11|(100q+r)$, so $11|n$. Then, $n$ can range from $10010$ to $99990$ for a total of $\boxed{8181\Rightarrow \mathrm{(B)}}$ numbers.

<3

Solution 1

When a $5$-digit number is divided by $100$, the first $3$ digits become the quotient, $q$, and the last $2$ digits become the remainder, $r$.

Therefore, $q$ can be any integer from $100$ to $999$ inclusive, and $r$ can be any integer from $0$ to $99$ inclusive.

For each of the $9\cdot10\cdot10=900$ possible values of $q$, there are at least $\left\lfloor \frac{100}{11} \right\rfloor = 9$ possible values of $r$ such that $q+r \equiv 0\pmod{11}$.

Since there is $1$ "extra" possible value of $r$ that is congruent to $0\pmod{11}$, each of the $\left\lfloor \frac{900}{11} \right\rfloor = 81$ values of $q$ that are congruent to $0\pmod{11}$ have $1$ more possible value of $r$ such that $q+r \equiv 0\pmod{11}$. Another way to think about it is the number of possible values of q when r, the remainder, is $0$. In this case, q itself has to be a multiple of $11$. $\left\lfloor \frac{999}{11} = 90 \right\rfloor$. Then we'll need to subtract $9$ from $90$ since we only want multiples of $11$ greater than $100$ $(90-9=81)$

Therefore, the number of possible values of $n$ such that $q+r \equiv 0\pmod{11}$ is $900\cdot9+81\cdot1=8181 \Rightarrow B$.

~ Minor Edit by PlainOldNumberTheory

Solution 2

Let $n$ equal $\overline{abcde}$, where $a$ through $e$ are digits. Therefore,

$q=\overline{abc}=100a+10b+c$

$r=\overline{de}=10d+e$

We now take $q+r\bmod{11}$:

$q+r=100a+10b+c+10d+e\equiv a-b+c-d+e\equiv 0\bmod{11}$

The divisor trick for 11 is as follows:

"Let $n=\overline{a_1a_2a_3\cdots a_x}$ be an $x$ digit integer. If $a_1-a_2+a_3-\cdots +(-1)^{x-1} a_x$ is divisible by $11$, then $n$ is also divisible by $11$."

Therefore, the five-digit number $n$ is divisible by 11. The 5-digit multiples of 11 range from $910\cdot 11$ to $9090\cdot 11$. There are $8181\Rightarrow \mathrm{(B)}$ divisors of 11 between those inclusive.

Note

The part labeled "divisor trick" actually follows from the same observation we made in the previous step: $10\equiv (-1)\pmod{11}$, therefore $10^{2k}\equiv 1$ and $10^{2k+1}\equiv (-1)$ for all $k$. For a $5-$digit number $\overline{abcde}$ we get $\overline{abcde}\equiv a\cdot 1 + b\cdot(-1) + c\cdot 1 + d\cdot(-1) + e\cdot 1 = a-b+c-d+e$, as claimed.

Also note that in the "divisor trick" we want to assign the signs backward - if we make sure that the last sign is a $+$, the result will have the same remainder modulo $11$ as the original number.

Solution 3

Since $q$ is a quotient and $r$ is a remainder when $n$ is divided by $100$. So we have $n=100q+r$. Since we are counting choices where $q+r$ is divisible by $11$, we have $n=99q+q+r=99q+11k$ for some $k$. This means that $n$ is the sum of two multiples of $11$ and would thus itself be a multiple of $11$. Then we can count all the five-digit multiples of $11$ as in Solution 2. (This solution is essentially the same as Solution 2, but it does not necessarily involve mods and so could potentially be faster.)

Solution 4

Defining $q$ and $r$ in terms of floor functions and $n$ would yield: $q=\left \lfloor \frac{n}{100} \right \rfloor$ and $r=n-100 \left \lfloor \frac{n}{100} \right \rfloor$. Since $q+r \equiv 0\pmod{11}$, $\left \lfloor \frac{n}{100} \right \rfloor + n-100 \left \lfloor \frac{n}{100} \right \rfloor \equiv 0\pmod{11}$. Simplifying gets us $n-99 \left \lfloor \frac{n}{100} \right \rfloor\equiv 0\pmod{11} \rightarrow n \equiv 0\pmod{11}$ ($99 \left \lfloor \frac{n}{100} \right \rfloor\equiv 0\pmod{11}$ is always true since floor function always yields an integer, and 99 is divisible by 11 w/o any remainder). After we come to this conclusion, it becomes easy to solve the rest of the problem ($\left \lfloor \frac{n}{99999} \right \rfloor - \left \lfloor \frac{n}{10000} \right \rfloor$). ~hw21

Video Solution 1

https://youtu.be/OpGHj-B0_hg?t=672

~IceMatrix

Video Solution 2

https://youtu.be/j5iM4V7ZT-Y

~savannahsolver

See Also

2003 AMC 10A (Problems • Answer Key • Resources)
Preceded by
Problem 24 		Followed by
Last Question
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions
2003 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 17 		Followed by
Problem 19
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2003_AMC_10A_Problems/Problem_25&oldid=193696"