Difference between revisions of "2003 AMC 10A Problems/Problem 25"
(→Solution 1) |
Megaboy6679 (talk | contribs) m |
||
(8 intermediate revisions by 6 users not shown) | |||
Line 6: | Line 6: | ||
== Solutions == | == Solutions == | ||
=== Simple Solution === | === Simple Solution === | ||
− | <math>11|q+r</math> implies that <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. | + | <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 | <3 | ||
Line 21: | Line 21: | ||
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 | + | ~ Minor Edit by PlainOldNumberTheory |
=== Solution 2 === | === Solution 2 === | ||
Line 38: | Line 38: | ||
"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>." | "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. | + | 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 ==== | ==== Note ==== | ||
Line 45: | Line 45: | ||
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. | 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 | + | 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 === | === 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.) | + | 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 == |
Latest revision as of 20:57, 29 May 2023
Contents
Problem
Let be a
-digit number, and let
and
be the quotient and the remainder, respectively, when
is divided by
. For how many values of
is
divisible by
?
Solutions
Simple Solution
implies that
and therefore
, so
. Then,
can range from
to
for a total of
numbers.
<3
Solution 1
When a -digit number is divided by
, the first
digits become the quotient,
, and the last
digits become the remainder,
.
Therefore, can be any integer from
to
inclusive, and
can be any integer from
to
inclusive.
For each of the possible values of
, there are at least
possible values of
such that
.
Since there is "extra" possible value of
that is congruent to
, each of the
values of
that are congruent to
have
more possible value of
such that
. Another way to think about it is the number of possible values of q when r, the remainder, is
. In this case, q itself has to be a multiple of
.
. Then we'll need to subtract
from
since we only want multiples of
greater than
Therefore, the number of possible values of such that
is
.
~ Minor Edit by PlainOldNumberTheory
Solution 2
Let equal
, where
through
are digits. Therefore,
We now take :
The divisor trick for 11 is as follows:
"Let be an
digit integer. If
is divisible by
, then
is also divisible by
."
Therefore, the five-digit number is divisible by 11. The 5-digit multiples of 11 range from
to
. There are
divisors of 11 between those inclusive.
Note
The part labeled "divisor trick" actually follows from the same observation we made in the previous step: , therefore
and
for all
.
For a
digit number
we get
, 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
as the original number.
Solution 3
Since is a quotient and
is a remainder when
is divided by
. So we have
. Since we are counting choices where
is divisible by
, we have
for some
. This means that
is the sum of two multiples of
and would thus itself be a multiple of
. Then we can count all the five-digit multiples of
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 and
in terms of floor functions and
would yield:
and
. Since
,
. Simplifying gets us
(
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 (
).
~hw21
Video Solution 1
https://youtu.be/OpGHj-B0_hg?t=672
~IceMatrix
Video Solution 2
~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.