Difference between revisions of "2021 Fall AMC 12B Problems/Problem 25"
Kevinmathz (talk | contribs) (→Solution) |
Xhypotenuse (talk | contribs) |
||
(8 intermediate revisions by 6 users not shown) | |||
Line 5: | Line 5: | ||
<math>\textbf{(A) }0\qquad\textbf{(B) }1\qquad\textbf{(C) }2\qquad\textbf{(D) }3\qquad\textbf{(E) }4</math> | <math>\textbf{(A) }0\qquad\textbf{(B) }1\qquad\textbf{(C) }2\qquad\textbf{(D) }3\qquad\textbf{(E) }4</math> | ||
− | ==Solution== | + | ==Solution 1== |
− | Note that we can add <math>9</math> to <math>R(n)</math> to get <math>R(n+1)</math>, but must subtract <math>k</math> for all <math>k|n+1</math>. Hence, we see that there are four ways to do that because <math>9=7+2=6+3=5+4=4+3+2</math>. Note that only <math>7+2</math> is a plausible option, since <math>4+3+2</math> indicates <math>n+1</math> is divisible by <math>6</math>, <math>5+4</math> indicates that <math>n+1</math> is divisible by <math>2</math>, <math>6+3</math> indicates <math>n+1</math> is | + | Note that we can add <math>9</math> to <math>R(n)</math> to get <math>R(n+1)</math>, but must subtract <math>k</math> for all <math>k|n+1</math>. Hence, we see that there are four ways to do that because <math>9=7+2=6+3=5+4=4+3+2</math>. Note that only <math>7+2</math> is a plausible option, since <math>4+3+2</math> indicates <math>n+1</math> is divisible by <math>6</math>, <math>5+4</math> indicates that <math>n+1</math> is divisible by <math>2</math>, <math>6+3</math> indicates <math>n+1</math> is divisible by <math>2</math>, and <math>9</math> itself indicates divisibility by <math>3</math>, too. So, <math>14|n+1</math> and <math>n+1</math> is not divisible by any positive integers from <math>2</math> to <math>10</math>, inclusive, except <math>2</math> and <math>7</math>. We check and get that only <math>n+1=14 \cdot 1</math> and <math>n+1=14 \cdot 7</math> give possible solutions so our answer is <math>\boxed{\textbf{(C) }2}</math>. |
- kevinmathz | - kevinmathz | ||
+ | |||
+ | == Solution 2 == | ||
+ | Denote by <math>{\rm Rem} \ \left( n, k \right)</math> the remainder of <math>n</math> divided by <math>k</math>. | ||
+ | Define <math>\Delta \left( n, k \right) = {\rm Rem} \ \left( n + 1, k \right) - {\rm Rem} \ \left( n, k \right)</math>. | ||
+ | |||
+ | Hence, | ||
+ | <cmath> | ||
+ | \[ | ||
+ | \Delta \left( n, k \right) | ||
+ | = \left\{ | ||
+ | \begin{array}{ll} | ||
+ | 1 & \mbox{ if } n \not\equiv -1 \pmod{k} \\ | ||
+ | - \left( k -1 \right) & \mbox{ if } n \equiv -1 \pmod{k} | ||
+ | \end{array} | ||
+ | \right.. | ||
+ | \] | ||
+ | </cmath> | ||
+ | |||
+ | Hence, this problem asks us to find all <math>n \in \left\{ 10 , 11, \cdots , 99 \right\}</math>, such that <math>\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0</math>. | ||
+ | |||
+ | <math>\textbf{Case 1}</math>: <math>\Delta \left( n, 10 \right) = - 9</math>. | ||
+ | |||
+ | We have <math>\sum_{k = 2}^9 \Delta \left( n, k \right) \leq \sum_{k = 2}^9 1 = 8</math>. | ||
+ | |||
+ | Therefore, there is no <math>n</math> in this case. | ||
+ | |||
+ | <math>\textbf{Case 2}</math>: <math>\Delta \left( n, 10 \right) = 1</math> and <math>\Delta \left( n, 9 \right) = -8</math>. | ||
+ | |||
+ | The condition <math>\Delta \left( n, 9 \right) = -8</math> implies <math>n \equiv - 1 \pmod{9}</math>. | ||
+ | This further implies <math>n \equiv - 1 \pmod{3}</math>. | ||
+ | Hence, <math>\Delta \left( n, 3 \right) = -2</math>. | ||
+ | |||
+ | To get <math>\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0</math>, we have <math>\sum_{k \in \left\{ 2 , 4 , 5 , 6, 7, 8\right\}} \Delta \left( n, k \right) = 9</math>. | ||
+ | |||
+ | However, we have <math>\sum_{k \in \left\{ 2 , 4 , 5 , 6, 7, 8\right\}} \Delta \left( n, k \right) \leq \sum_{k \in \left\{ 2 , 4 , 5 , 6, 7, 8\right\}} 1 = 6</math>. | ||
+ | |||
+ | Therefore, there is no <math>n</math> in this case. | ||
+ | |||
+ | <math>\textbf{Case 3}</math>: <math>\Delta \left( n, k \right) = 1</math> for <math>k \in \left\{ 9 , 10 \right\}</math> and <math>\Delta \left( n, 8 \right) = -7</math>. | ||
+ | |||
+ | The condition <math>\Delta \left( n, 8 \right) = -7</math> implies <math>n \equiv - 1 \pmod{k}</math> with <math>k \in \left\{ 2, 4 \right\}</math>. | ||
+ | Hence, <math>\Delta \left( n, 2 \right) = -1</math> and <math>\Delta \left( n, 4 \right) = -3</math>. | ||
+ | |||
+ | To get <math>\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0</math>, we have <math>\sum_{k \in \left\{ 3, 5, 6, 7 \right\}} \Delta \left( n, k \right) = 9</math>. | ||
+ | |||
+ | However, we have <math>\sum_{k \in \left\{ 3, 5, 6, 7 \right\}} \Delta \left( n, k \right) \leq \sum_{k \in \left\{ 3, 5, 6, 7 \right\}} 1 = 4</math>. | ||
+ | |||
+ | Therefore, there is no <math>n</math> in this case. | ||
+ | |||
+ | <math>\textbf{Case 4}</math>: <math>\Delta \left( n, k \right) = 1</math> for <math>k \in \left\{ 8, \cdots , 10 \right\}</math> and <math>\Delta \left( n, 7 \right) = -6</math>. | ||
+ | |||
+ | To get <math>\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0</math>, we have <math>\sum_{k \in \left\{ 2, 3, 4, 5, 6 \right\}} \Delta \left( n, k \right) = 3</math>. | ||
+ | |||
+ | Hence, we must have <math>\Delta \left( n, 2 \right) = -1</math> and <math>\Delta \left( n, k \right) = 1</math> for <math>k \in \left\{ 3 , 4 , 5 , 6 \right\}</math>. | ||
+ | |||
+ | Therefore, <math>n = 13, 97</math>. | ||
+ | |||
+ | <math>\textbf{Case 5}</math>: <math>\Delta \left( n, k \right) = 1</math> for <math>k \in \left\{ 7 , \cdots , 10 \right\}</math> and <math>\Delta \left( n, 6 \right) = -5</math>. | ||
+ | |||
+ | The condition <math>\Delta \left( n, 6 \right) = -5</math> implies <math>n \equiv - 1 \pmod{k}</math> with <math>k \in \left\{ 2, 3 \right\}</math>. | ||
+ | Hence, <math>\Delta \left( n, 2 \right) = -1</math> and <math>\Delta \left( n, 3 \right) = -2</math>. | ||
+ | |||
+ | To get <math>\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0</math>, we have <math>\sum_{k \in \left\{ 4, 5 \right\}} \Delta \left( n, k \right) = 4</math>. | ||
+ | |||
+ | However, we have <math>\sum_{k \in \left\{ 4, 5 \right\}} \Delta \left( n, k \right) \leq \sum_{k \in \left\{ 4, 5 \right\}} 1 = 2</math>. | ||
+ | |||
+ | Therefore, there is no <math>n</math> in this case. | ||
+ | |||
+ | |||
+ | <math>\textbf{Case 6}</math>: <math>\Delta \left( n, k \right) = 1</math> for <math>k \in \left\{ 6 , \cdots , 10 \right\}</math> and <math>\Delta \left( n, 5 \right) = -4</math>. | ||
+ | |||
+ | To get <math>\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0</math>, we have <math>\sum_{k \in \left\{ 2, 3, 4 \right\}} \Delta \left( n, k \right) = -1</math>. | ||
+ | |||
+ | This can be achieved if <math>\Delta \left( n, 2 \right) = 1</math>, <math>\Delta \left( n, 3 \right) = 1</math>, <math>\Delta \left( n, 4 \right) = -3</math>. | ||
+ | |||
+ | However, <math>\Delta \left( n, 4 \right) = -3</math> implies <math>n \equiv - 1 \pmod{4}</math>. This implies <math>n \equiv -1 \pmod{2}</math>. Hence, <math>\Delta \left( n, 2 \right) = -1</math>. | ||
+ | We get a contradiction. | ||
+ | |||
+ | Therefore, there is no <math>n</math> in this case. | ||
+ | |||
+ | <math>\textbf{Case 7}</math>: <math>\Delta \left( n, k \right) = 1</math> for <math>k \in \left\{ 5 , \cdots , 10 \right\}</math> and <math>\Delta \left( n, 4 \right) = -3</math>. | ||
+ | |||
+ | The condition <math>\Delta \left( n, 4 \right) = -3</math> implies <math>n \equiv - 1 \pmod{k}</math> with <math>k = 2</math>. | ||
+ | Hence, <math>\Delta \left( n, 2 \right) = -1</math>. | ||
+ | |||
+ | To get <math>\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0</math>, we have <math>\Delta \left( n, 3 \right) = - 2</math>. This implies <math>n \equiv - 1 \pmod{3}</math>. | ||
+ | |||
+ | Because <math>n \equiv - 1 \pmod{2}</math> and <math>n \equiv - 1 \pmod{3}</math>, we have <math>n \equiv - 1 \pmod{6}</math>. | ||
+ | Hence, <math>\Delta \left( n, 6 \right) = - 5</math>. | ||
+ | However, in this case, we assume <math>\Delta \left( n, 6 \right) = 1</math>. | ||
+ | We get a contradiction. | ||
+ | |||
+ | Therefore, there is no <math>n</math> in this case. | ||
+ | |||
+ | <math>\textbf{Case 8}</math>: <math>\Delta \left( n, k \right) = 1</math> for <math>k \in \left\{ 4 , \cdots , 10 \right\}</math> and <math>\Delta \left( n, 3 \right) = -2</math>. | ||
+ | |||
+ | To get <math>\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0</math>, we have <math>\Delta \left( n, 2 \right) = - 5</math>. This is infeasible. | ||
+ | |||
+ | Therefore, there is no <math>n</math> in this case. | ||
+ | |||
+ | <math>\textbf{Case 9}</math>: <math>\Delta \left( n, k \right) = 1</math> for <math>k \in \left\{3 , \cdots , 10 \right\}</math>. | ||
+ | |||
+ | To get <math>\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0</math>, we have <math>\Delta \left( n, 2 \right) = - 8</math>. This is infeasible. | ||
+ | |||
+ | Therefore, there is no <math>n</math> in this case. | ||
+ | |||
+ | Putting all cases together, the answer is <math>\boxed{\textbf{(C) }2}</math>. | ||
+ | |||
+ | ~Steven Chen (www.professorchenedu.com) | ||
+ | |||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | To get from <math>n</math> to <math>n+1</math>, <math>R(n)</math> would add by <math>9</math> for each remainder <math>2, 3, 4, 5, 6, 7, 8, 9, 10</math>. However, given that some of these remainders can "round down" to <math>0</math> given the nature of mods, we must calculate the possible values of <math>n</math> such that the remainders in <math>R(n+1)</math> "rounds down" by a total of <math>9</math>, effectively canceling out the adding by <math>9</math> initially. | ||
+ | |||
+ | |||
+ | To do so, we will analyze the "rounding down" for each of <math>2, 3, 4, 5, 6, 7, 8, 9, 10</math>: | ||
+ | |||
+ | |||
+ | <math>n+1 \equiv 0 \pmod 2</math>: subtract by <math>2</math> | ||
+ | |||
+ | <math>n+1 \equiv 0 \pmod 3</math>: subtract by <math>3</math> | ||
+ | |||
+ | <math>n+1 \equiv 0 \pmod 4</math>: subtract by <math>4</math>, but this also implies mod <math>2</math>, so subtract by <math>6</math>. | ||
+ | |||
+ | <math>n+1 \equiv 0 \pmod 5</math>: subtract by <math>5</math> | ||
+ | |||
+ | <math>n+1 \equiv 0 \pmod 6</math>: subtract by <math>6</math>, but this also implies mod <math>2</math> and <math>3</math>, so subtract by <math>11</math>: too much | ||
+ | |||
+ | <math>n+1 \equiv 0 \pmod 7</math>: subtract by <math>7</math> | ||
+ | |||
+ | <math>n+1 \equiv 0 \pmod 8</math>: subtract by <math>8</math>, but this also implies mod <math>2</math> and <math>4</math>, so subtract by <math>14</math>: too much | ||
+ | |||
+ | <math>n+1 \equiv 0 \pmod 9</math>: subtract by <math>9</math>, but this also implies mod <math>3</math>, so subtract by <math>12</math>: too much | ||
+ | |||
+ | <math>n+1 \equiv 0 \pmod {10}</math>: subtract by <math>10</math>: too much | ||
+ | |||
+ | |||
+ | |||
+ | Notice that <math>9 = 7+2 = 6+3 = 5+4 = 4+3+2</math>. By testing these sums, we can easily show that the only time when the total subtraction is <math>9</math> is when <math>n+1 \equiv 0 \pmod 2</math> AND <math>n+1 \equiv 0 \pmod 7</math>. By CRT, <math>n+1 \equiv 0 \pmod {14}</math>: | ||
+ | |||
+ | |||
+ | As in solution 1, then, only <math>n+1=14 \cdot 1</math> and <math>n+1=14 \cdot 7</math> give possible solutions, so our answer is <math>\boxed{\textbf{(C) }2}</math>. | ||
+ | |||
+ | |||
+ | ~xHypotenuse | ||
+ | |||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/vRKB4JdUIJ4 | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
+ | |||
+ | |||
+ | ==Video Solution by Mathematical Dexterity== | ||
+ | https://www.youtube.com/watch?v=Fy8wU4VAzkQ | ||
{{AMC12 box|year=2021 Fall|ab=B|num-b=24|after=Last problem}} | {{AMC12 box|year=2021 Fall|ab=B|num-b=24|after=Last problem}} | ||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 01:16, 21 August 2024
Contents
Problem
For a positive integer, let
be the sum of the remainders when
is divided by
,
,
,
,
,
,
,
, and
. For example,
. How many two-digit positive integers
satisfy
Solution 1
Note that we can add to
to get
, but must subtract
for all
. Hence, we see that there are four ways to do that because
. Note that only
is a plausible option, since
indicates
is divisible by
,
indicates that
is divisible by
,
indicates
is divisible by
, and
itself indicates divisibility by
, too. So,
and
is not divisible by any positive integers from
to
, inclusive, except
and
. We check and get that only
and
give possible solutions so our answer is
.
- kevinmathz
Solution 2
Denote by the remainder of
divided by
.
Define
.
Hence,
Hence, this problem asks us to find all , such that
.
:
.
We have .
Therefore, there is no in this case.
:
and
.
The condition implies
.
This further implies
.
Hence,
.
To get , we have
.
However, we have .
Therefore, there is no in this case.
:
for
and
.
The condition implies
with
.
Hence,
and
.
To get , we have
.
However, we have .
Therefore, there is no in this case.
:
for
and
.
To get , we have
.
Hence, we must have and
for
.
Therefore, .
:
for
and
.
The condition implies
with
.
Hence,
and
.
To get , we have
.
However, we have .
Therefore, there is no in this case.
:
for
and
.
To get , we have
.
This can be achieved if ,
,
.
However, implies
. This implies
. Hence,
.
We get a contradiction.
Therefore, there is no in this case.
:
for
and
.
The condition implies
with
.
Hence,
.
To get , we have
. This implies
.
Because and
, we have
.
Hence,
.
However, in this case, we assume
.
We get a contradiction.
Therefore, there is no in this case.
:
for
and
.
To get , we have
. This is infeasible.
Therefore, there is no in this case.
:
for
.
To get , we have
. This is infeasible.
Therefore, there is no in this case.
Putting all cases together, the answer is .
~Steven Chen (www.professorchenedu.com)
Solution 3
To get from to
,
would add by
for each remainder
. However, given that some of these remainders can "round down" to
given the nature of mods, we must calculate the possible values of
such that the remainders in
"rounds down" by a total of
, effectively canceling out the adding by
initially.
To do so, we will analyze the "rounding down" for each of :
: subtract by
: subtract by
: subtract by
, but this also implies mod
, so subtract by
.
: subtract by
: subtract by
, but this also implies mod
and
, so subtract by
: too much
: subtract by
: subtract by
, but this also implies mod
and
, so subtract by
: too much
: subtract by
, but this also implies mod
, so subtract by
: too much
: subtract by
: too much
Notice that . By testing these sums, we can easily show that the only time when the total subtraction is
is when
AND
. By CRT,
:
As in solution 1, then, only and
give possible solutions, so our answer is
.
~xHypotenuse
Video Solution
~MathProblemSolvingSkills.com
Video Solution by Mathematical Dexterity
https://www.youtube.com/watch?v=Fy8wU4VAzkQ
2021 Fall AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 24 |
Followed by Last problem |
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.