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 "2021 Fall AMC 12B Problems/Problem 25"

(→‎Solution)
 
(4 intermediate revisions by 4 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 divisibly 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 divisibly 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>.
+
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)
 +
 +
 +
==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 00:38, 6 January 2023

Problem

For $n$ a positive integer, let $R(n)$ be the sum of the remainders when $n$ is divided by $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, and $10$. For example, $R(15) = 1+0+3+0+3+1+7+6+5=26$. How many two-digit positive integers $n$ satisfy $R(n) = R(n+1)\,?$

$\textbf{(A) }0\qquad\textbf{(B) }1\qquad\textbf{(C) }2\qquad\textbf{(D) }3\qquad\textbf{(E) }4$

Solution 1

Note that we can add $9$ to $R(n)$ to get $R(n+1)$, but must subtract $k$ for all $k|n+1$. Hence, we see that there are four ways to do that because $9=7+2=6+3=5+4=4+3+2$. Note that only $7+2$ is a plausible option, since $4+3+2$ indicates $n+1$ is divisible by $6$, $5+4$ indicates that $n+1$ is divisible by $2$, $6+3$ indicates $n+1$ is divisible by $2$, and $9$ itself indicates divisibility by $3$, too. So, $14|n+1$ and $n+1$ is not divisible by any positive integers from $2$ to $10$, inclusive, except $2$ and $7$. We check and get that only $n+1=14 \cdot 1$ and $n+1=14 \cdot 7$ give possible solutions so our answer is $\boxed{\textbf{(C) }2}$.

- kevinmathz

Solution 2

Denote by ${\rm Rem} \ \left( n, k \right)$ the remainder of $n$ divided by $k$. Define $\Delta \left( n, k \right) = {\rm Rem} \ \left( n + 1, k \right) - {\rm Rem} \ \left( n, k \right)$.

Hence, \[ \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.. \]

Hence, this problem asks us to find all $n \in \left\{ 10 , 11, \cdots , 99 \right\}$, such that $\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0$.

$\textbf{Case 1}$: $\Delta \left( n, 10 \right) = - 9$.

We have $\sum_{k = 2}^9 \Delta \left( n, k \right) \leq \sum_{k = 2}^9 1 = 8$.

Therefore, there is no $n$ in this case.

$\textbf{Case 2}$: $\Delta \left( n, 10 \right) = 1$ and $\Delta \left( n, 9 \right) = -8$.

The condition $\Delta \left( n, 9 \right) = -8$ implies $n \equiv - 1 \pmod{9}$. This further implies $n \equiv - 1 \pmod{3}$. Hence, $\Delta \left( n, 3 \right) = -2$.

To get $\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0$, we have $\sum_{k \in \left\{ 2 , 4 , 5 , 6, 7, 8\right\}} \Delta \left( n, k \right) = 9$.

However, we have $\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$.

Therefore, there is no $n$ in this case.

$\textbf{Case 3}$: $\Delta \left( n, k \right) = 1$ for $k \in \left\{ 9 , 10 \right\}$ and $\Delta \left( n, 8 \right) = -7$.

The condition $\Delta \left( n, 8 \right) = -7$ implies $n \equiv - 1 \pmod{k}$ with $k \in \left\{ 2, 4 \right\}$. Hence, $\Delta \left( n, 2 \right) = -1$ and $\Delta \left( n, 4 \right) = -3$.

To get $\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0$, we have $\sum_{k \in \left\{ 3, 5, 6, 7 \right\}} \Delta \left( n, k \right) = 9$.

However, we have $\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$.

Therefore, there is no $n$ in this case.

$\textbf{Case 4}$: $\Delta \left( n, k \right) = 1$ for $k \in \left\{ 8, \cdots , 10 \right\}$ and $\Delta \left( n, 7 \right) = -6$.

To get $\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0$, we have $\sum_{k \in \left\{ 2, 3, 4, 5, 6 \right\}} \Delta \left( n, k \right) = 3$.

Hence, we must have $\Delta \left( n, 2 \right) = -1$ and $\Delta \left( n, k \right) = 1$ for $k \in \left\{ 3 , 4 , 5 , 6 \right\}$.

Therefore, $n = 13, 97$.

$\textbf{Case 5}$: $\Delta \left( n, k \right) = 1$ for $k \in \left\{ 7 , \cdots , 10 \right\}$ and $\Delta \left( n, 6 \right) = -5$.

The condition $\Delta \left( n, 6 \right) = -5$ implies $n \equiv - 1 \pmod{k}$ with $k \in \left\{ 2, 3 \right\}$. Hence, $\Delta \left( n, 2 \right) = -1$ and $\Delta \left( n, 3 \right) = -2$.

To get $\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0$, we have $\sum_{k \in \left\{ 4, 5 \right\}} \Delta \left( n, k \right) = 4$.

However, we have $\sum_{k \in \left\{ 4, 5 \right\}} \Delta \left( n, k \right) \leq \sum_{k \in \left\{ 4, 5 \right\}} 1 = 2$.

Therefore, there is no $n$ in this case.


$\textbf{Case 6}$: $\Delta \left( n, k \right) = 1$ for $k \in \left\{ 6 , \cdots , 10 \right\}$ and $\Delta \left( n, 5 \right) = -4$.

To get $\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0$, we have $\sum_{k \in \left\{ 2, 3, 4 \right\}} \Delta \left( n, k \right) = -1$.

This can be achieved if $\Delta \left( n, 2 \right) = 1$, $\Delta \left( n, 3 \right) = 1$, $\Delta \left( n, 4 \right) = -3$.

However, $\Delta \left( n, 4 \right) = -3$ implies $n \equiv - 1 \pmod{4}$. This implies $n \equiv -1 \pmod{2}$. Hence, $\Delta \left( n, 2 \right) = -1$. We get a contradiction.

Therefore, there is no $n$ in this case.

$\textbf{Case 7}$: $\Delta \left( n, k \right) = 1$ for $k \in \left\{ 5 , \cdots , 10 \right\}$ and $\Delta \left( n, 4 \right) = -3$.

The condition $\Delta \left( n, 4 \right) = -3$ implies $n \equiv - 1 \pmod{k}$ with $k = 2$. Hence, $\Delta \left( n, 2 \right) = -1$.

To get $\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0$, we have $\Delta \left( n, 3 \right) = - 2$. This implies $n \equiv - 1 \pmod{3}$.

Because $n \equiv - 1 \pmod{2}$ and $n \equiv - 1 \pmod{3}$, we have $n \equiv - 1 \pmod{6}$. Hence, $\Delta \left( n, 6 \right) = - 5$. However, in this case, we assume $\Delta \left( n, 6 \right) = 1$. We get a contradiction.

Therefore, there is no $n$ in this case.

$\textbf{Case 8}$: $\Delta \left( n, k \right) = 1$ for $k \in \left\{ 4 , \cdots , 10 \right\}$ and $\Delta \left( n, 3 \right) = -2$.

To get $\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0$, we have $\Delta \left( n, 2 \right) = - 5$. This is infeasible.

Therefore, there is no $n$ in this case.

$\textbf{Case 9}$: $\Delta \left( n, k \right) = 1$ for $k \in \left\{3 , \cdots , 10 \right\}$.

To get $\sum_{k = 2}^{10} \Delta \left( n, k \right) = 0$, we have $\Delta \left( n, 2 \right) = - 8$. This is infeasible.

Therefore, there is no $n$ in this case.

Putting all cases together, the answer is $\boxed{\textbf{(C) }2}$.

~Steven Chen (www.professorchenedu.com)


Video Solution

https://youtu.be/vRKB4JdUIJ4

~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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_Fall_AMC_12B_Problems/Problem_25&oldid=185903"