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 10B Problems/Problem 22"

(Created page with "==Problem== For each integer <math> n\geq 2 </math>, let <math> S_n </math> be the sum of all products <math> jk </math>, where <math> j </math> and <math> k </math> are integ...")
 
m (→‎Solution 1)
 
(9 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
 
For each integer <math> n\geq 2 </math>, let <math> S_n </math> be the sum of all products <math> jk </math>, where <math> j </math> and <math> k </math> are integers and <math> 1\leq j<k\leq n </math>. What is the sum of the 10 least values of <math> n </math> such that <math> S_n </math> is divisible by <math> 3 </math>?
 
For each integer <math> n\geq 2 </math>, let <math> S_n </math> be the sum of all products <math> jk </math>, where <math> j </math> and <math> k </math> are integers and <math> 1\leq j<k\leq n </math>. What is the sum of the 10 least values of <math> n </math> such that <math> S_n </math> is divisible by <math> 3 </math>?
 +
 
<math>\textbf{(A)}\ 196\qquad\textbf{(B)}\ 197\qquad\textbf{(C)}\ 198\qquad\textbf{(D)}\ 199\qquad\textbf{(E)}\ 200</math>
 
<math>\textbf{(A)}\ 196\qquad\textbf{(B)}\ 197\qquad\textbf{(C)}\ 198\qquad\textbf{(D)}\ 199\qquad\textbf{(E)}\ 200</math>
  
Line 9: Line 10:
 
<cmath>\frac{1\cdot {2}^2}{2}\equiv 2\pmod{3}.</cmath>
 
<cmath>\frac{1\cdot {2}^2}{2}\equiv 2\pmod{3}.</cmath>
  
−
Clearly, <math> S_2\equiv 2\pmod{3}. </math> Using the above result, we have <math> S_5\equiv 1\pmod{3} </math>, and <math> S_8 </math>, <math> S_9 </math>, and <math> S_{10} </math> are all divisible by <math> 3 </math>. After <math> 3\cdot 3=9 </math>, we have <math> S_{17} </math>, <math> S_{18} </math>, and <math> S_{19} </math> all divisible by <math> 3 </math>, as well as <math> S_{26}, S_{27}, S_{28} </math>, and <math> S_{35} </math>. Thus, our answer is <math> 8+9+10+17+18+19+26+27+28+35=27+54+81+35=162+35=\boxed{\mathrm{(B)}\ 197} </math>. -BorealBear
+
Clearly, <math> S_2\equiv 2\pmod{3}. </math> Using the above result, we have <math> S_5\equiv 1\pmod{3} </math>, and <math> S_8 </math>, <math> S_9 </math>, and <math> S_{10} </math> are all divisible by <math> 3 </math>. After <math> 3\cdot 3=9 </math>, we have <math> S_{17} </math>, <math> S_{18} </math>, and <math> S_{19} </math> all divisible by <math> 3 </math>, as well as <math> S_{26}, S_{27}, S_{28} </math>, and <math> S_{35} </math>. Thus, our answer is <math> 8+9+10+17+18+19+26+27+28+35=27+54+81+35=162+35=\boxed{\mathrm{(B)}\ 197} .</math> -BorealBear
 +
 
 +
-minor edit by [[User: Yiyj1|Yiyj1]]
 +
 
 +
==Solution 2 (bash)==
 +
Since we have a wonky function, we start by trying out some small cases and see what happens. If <math>j</math> is <math>1</math> and <math>k</math> is <math>2</math>, then there is one case. We have <math>2</math> mod <math>3</math> for this case. If <math>N</math> is <math>3</math>, we have <math>1 \cdot 2 + 1 \cdot 3 + 2 \cdot 3</math> which is still <math>2</math> mod <math>3</math>. If <math>N</math> is <math>4</math>, we have to add <math>1 \cdot 4 + 2 \cdot 4 + 3 \cdot 4</math> which is a multiple of <math>3</math>, meaning that we are still at <math>2</math> mod <math>3</math>. If we try a few more cases, we find that when <math>N</math> is <math>8</math>, we get a multiple of <math>3</math>. When <math>N</math> is <math>9</math>, we are adding <math>0</math> mod <math>3</math>, and therefore, we are still at a multiple of <math>3</math>.
 +
 
 +
When <math>N</math> is <math>10</math>, then we get <math>0</math> mod <math>3</math> + <math>10(1+2+3+...+9)</math> which is <math>10</math> times a multiple of <math>3</math>. Therefore, we have another multiple of <math>3</math>. When <math>N</math> is <math>11</math>, so we have <math>2</math> mod <math>3</math>. So, every time we have <math>-1</math> mod <math>9</math>, <math>0</math> mod <math>9</math>, and <math>1</math> mod <math>9</math>, we always have a multiple of <math>3</math>. Think about it: When <math>N</math> is <math>1</math>, it will have to be <math>0 \cdot 1</math>, so it is a multiple of <math>3</math>. Therefore, our numbers are <math>8, 9, 10, 17, 18, 19, 26, 27, 28, 35</math>. Adding the numbers up, we get <math>\boxed{\textbf{(B) 197}}</math>
 +
 
 +
~Arcticturn
 +
 
 +
== Solution 3 ==
 +
Denote <math>A_{n, <} = \left\{ \left( j , k \right) : 1 \leq j < k \leq n \right\}</math>, <math>A_{n, >} = \left\{ \left( j , k \right) : 1 \leq k < j \leq n \right\}</math> and <math>A_{n, =} = \left\{ \left( j , k \right) : 1 \leq j = k \leq n \right\}</math>.
 +
 
 +
Hence, <math>\sum_{\left( j , k \right) \in A_{n,<}} jk = \sum_{\left( j , k \right) \in A_{n,>}} jk = S_n</math>.
 +
 
 +
Therefore,
 +
<cmath>
 +
\begin{align*}
 +
S_n & = \frac{1}{2} \left( \sum_{\left( j , k \right) \in A_{n,<}} jk = \sum_{\left( j , k \right) \in A_{n,>}} jk \right) \\
 +
& = \frac{1}{2} \left( \sum_{1 \leq j, k \leq n} jk - {\left( j , k \right) \in A_{n,=}} jk \right) \\
 +
& = \frac{1}{2} \left( \sum_{j=1}^n \sum_{k=1}^n jk - \sum_{j=1}^n j^2 \right) \\
 +
& = \frac{1}{2} \left( \frac{n^2 \left( n + 1 \right)^2}{4}
 +
- \frac{n \left( n + 1 \right) \left( 2 n + 1 \right) }{6} \right) \\
 +
& = \frac{\left( n - 1 \right) n \left( n + 1 \right) \left( 3 n + 2 \right)}{24} .
 +
\end{align*}
 +
</cmath>
 +
 
 +
Hence, <math>S_n</math> is divisible by 3 if and only if <math>\left( n - 1 \right) n \left( n + 1 \right) \left( 3 n + 2 \right)</math> is divisible by <math>24 \cdot 3 = 8 \cdot 9</math>.
 +
 
 +
First, <math>\left( n - 1 \right) n \left( n + 1 \right) \left( 3 n + 2 \right)</math> is always divisible by 8. Otherwise, <math>S_n</math> is not even an integer.
 +
 
 +
Second, we find conditions for <math>n</math>, such that <math>\left( n - 1 \right) n \left( n + 1 \right) \left( 3 n + 2 \right)</math> is divisible by 9.
 +
 
 +
Because <math>3 n + 2</math> is not divisible by 3, it cannot be divisible by 9.
 +
 
 +
Hence, we need to find conditions for <math>n</math>, such that <math>\left( n - 1 \right) n \left( n + 1 \right)</math> is divisible by 9.
 +
This holds of <math>n \equiv 0, \pm 1 \pmod{9}</math>.
 +
 
 +
Therefore, the 10 least values of <math>n</math> such that <math>\left( n - 1 \right) n \left( n + 1 \right)</math> is divisible by 9 (equivalently, <math>S_n</math> is divisible by 3) are 8, 9, 10, 17, 18, 19, 26, 27, 28, 35.
 +
Their sum is 197.
 +
 
 +
Therefore, the answer is <math>\boxed{\textbf{(B) }197}</math>.
 +
 
 +
~Steven Chen (www.professorchenedu.com)
 +
 
 +
==Video Solution by Interstigation==
 +
https://youtu.be/_PDIrta6r8s
 +
 
 +
~Interstigation
 +
 
 +
==Video Solution 2 by WhyMath==
 +
https://youtu.be/M8tF1uSOfXA
 +
 
 +
~savannahsolver
  
 
==See Also==
 
==See Also==
 
{{AMC10 box|year=2021 Fall|ab=B|num-b=21|num-a=23}}
 
{{AMC10 box|year=2021 Fall|ab=B|num-b=21|num-a=23}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 17:36, 13 November 2023

Problem

For each integer $n\geq 2$, let $S_n$ be the sum of all products $jk$, where $j$ and $k$ are integers and $1\leq j<k\leq n$. What is the sum of the 10 least values of $n$ such that $S_n$ is divisible by $3$?

$\textbf{(A)}\ 196\qquad\textbf{(B)}\ 197\qquad\textbf{(C)}\ 198\qquad\textbf{(D)}\ 199\qquad\textbf{(E)}\ 200$

Solution 1

To get from $S_n$ to $S_{n+1}$, we add $1(n+1)+2(n+1)+\cdots +n(n+1)=(1+2+\cdots +n)(n+1)=\frac{n(n+1)^2}{2}$.

Now, we can look at the different values of $n$ mod $3$. For $n\equiv 0\pmod{3}$ and $n\equiv 2\pmod{3}$, then we have $\frac{n(n+1)^2}{2}\equiv 0\pmod{3}$. However, for $n\equiv 1\pmod{3}$, we have \[\frac{1\cdot {2}^2}{2}\equiv 2\pmod{3}.\]

Clearly, $S_2\equiv 2\pmod{3}.$ Using the above result, we have $S_5\equiv 1\pmod{3}$, and $S_8$, $S_9$, and $S_{10}$ are all divisible by $3$. After $3\cdot 3=9$, we have $S_{17}$, $S_{18}$, and $S_{19}$ all divisible by $3$, as well as $S_{26}, S_{27}, S_{28}$, and $S_{35}$. Thus, our answer is $8+9+10+17+18+19+26+27+28+35=27+54+81+35=162+35=\boxed{\mathrm{(B)}\ 197} .$ -BorealBear

-minor edit by Yiyj1

Solution 2 (bash)

Since we have a wonky function, we start by trying out some small cases and see what happens. If $j$ is $1$ and $k$ is $2$, then there is one case. We have $2$ mod $3$ for this case. If $N$ is $3$, we have $1 \cdot 2 + 1 \cdot 3 + 2 \cdot 3$ which is still $2$ mod $3$. If $N$ is $4$, we have to add $1 \cdot 4 + 2 \cdot 4 + 3 \cdot 4$ which is a multiple of $3$, meaning that we are still at $2$ mod $3$. If we try a few more cases, we find that when $N$ is $8$, we get a multiple of $3$. When $N$ is $9$, we are adding $0$ mod $3$, and therefore, we are still at a multiple of $3$.

When $N$ is $10$, then we get $0$ mod $3$ + $10(1+2+3+...+9)$ which is $10$ times a multiple of $3$. Therefore, we have another multiple of $3$. When $N$ is $11$, so we have $2$ mod $3$. So, every time we have $-1$ mod $9$, $0$ mod $9$, and $1$ mod $9$, we always have a multiple of $3$. Think about it: When $N$ is $1$, it will have to be $0 \cdot 1$, so it is a multiple of $3$. Therefore, our numbers are $8, 9, 10, 17, 18, 19, 26, 27, 28, 35$. Adding the numbers up, we get $\boxed{\textbf{(B) 197}}$

~Arcticturn

Solution 3

Denote $A_{n, <} = \left\{ \left( j , k \right) : 1 \leq j < k \leq n \right\}$, $A_{n, >} = \left\{ \left( j , k \right) : 1 \leq k < j \leq n \right\}$ and $A_{n, =} = \left\{ \left( j , k \right) : 1 \leq j = k \leq n \right\}$.

Hence, $\sum_{\left( j , k \right) \in A_{n,<}} jk = \sum_{\left( j , k \right) \in A_{n,>}} jk = S_n$.

Therefore, \begin{align*} S_n & = \frac{1}{2} \left( \sum_{\left( j , k \right) \in A_{n,<}} jk = \sum_{\left( j , k \right) \in A_{n,>}} jk \right) \\ & = \frac{1}{2} \left( \sum_{1 \leq j, k \leq n} jk - {\left( j , k \right) \in A_{n,=}} jk \right) \\ & = \frac{1}{2} \left( \sum_{j=1}^n \sum_{k=1}^n jk - \sum_{j=1}^n j^2 \right) \\ & = \frac{1}{2} \left( \frac{n^2 \left( n + 1 \right)^2}{4} - \frac{n \left( n + 1 \right) \left( 2 n + 1 \right) }{6} \right) \\ & = \frac{\left( n - 1 \right) n \left( n + 1 \right) \left( 3 n + 2 \right)}{24} . \end{align*}

Hence, $S_n$ is divisible by 3 if and only if $\left( n - 1 \right) n \left( n + 1 \right) \left( 3 n + 2 \right)$ is divisible by $24 \cdot 3 = 8 \cdot 9$.

First, $\left( n - 1 \right) n \left( n + 1 \right) \left( 3 n + 2 \right)$ is always divisible by 8. Otherwise, $S_n$ is not even an integer.

Second, we find conditions for $n$, such that $\left( n - 1 \right) n \left( n + 1 \right) \left( 3 n + 2 \right)$ is divisible by 9.

Because $3 n + 2$ is not divisible by 3, it cannot be divisible by 9.

Hence, we need to find conditions for $n$, such that $\left( n - 1 \right) n \left( n + 1 \right)$ is divisible by 9. This holds of $n \equiv 0, \pm 1 \pmod{9}$.

Therefore, the 10 least values of $n$ such that $\left( n - 1 \right) n \left( n + 1 \right)$ is divisible by 9 (equivalently, $S_n$ is divisible by 3) are 8, 9, 10, 17, 18, 19, 26, 27, 28, 35. Their sum is 197.

Therefore, the answer is $\boxed{\textbf{(B) }197}$.

~Steven Chen (www.professorchenedu.com)

Video Solution by Interstigation

https://youtu.be/_PDIrta6r8s

~Interstigation

Video Solution 2 by WhyMath

https://youtu.be/M8tF1uSOfXA

~savannahsolver

See Also

2021 Fall AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 21 		Followed by
Problem 23
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

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_10B_Problems/Problem_22&oldid=203025"