2003 AMC 10A Problems/Problem 25

Revision as of 14:00, 1 August 2011 by Joshxiong (talk | contribs) (See Also)

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$

Solution

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}$.

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

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.

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 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.)

Notes

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 actually want to assign the signs backwards - if we make sure that the last sign is a $+$, the result will have the same remainder modulo $11$ as the original number.

See Also

2003 AMC 10A (ProblemsAnswer KeyResources)
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
Invalid username
Login to AoPS