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"

(→‎Solution 3)
m
 
(35 intermediate revisions by 21 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 12: Line 17:
 
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>.  
 
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>.  
+
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>
 +
 
 +
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 ===
Line 29: Line 36:
 
The divisor trick for 11 is as follows:
 
The divisor trick for 11 is as follows:
  
−
"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 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.
 +
 
 +
=== Solution 3 ===
  
−
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.
+
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 3====
+
=== Solution 4 ===
  
−
Since q is a quotient and r is a remainder when n is divided by 100. So we have <math>n=100q+r</math>. Since we are counting choices where q+r is divisible by 11, we have <math>n=99q+q+r=99q+11k</math> for some k. This means that n is the sum of two multiples of 11 and would thus itself be a divisor of 11. Then we can count all the four digit divisors 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.)
+
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
  
−
==== Notes ====
+
==Video Solution 1==
 +
https://youtu.be/OpGHj-B0_hg?t=672
  
−
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>.  
+
~IceMatrix
−
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.
+
 
 +
==Video Solution 2==
 +
https://youtu.be/j5iM4V7ZT-Y
  
−
Also note that in the "divisor trick" we actually want to assign the signs backwards - 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.
+
~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"