Difference between revisions of "2022 AIME II Problems/Problem 10"

Line 4: Line 4:
  
 
==Solution==
 
==Solution==
 +
To solve this problem, we need to use the following result:
 +
 +
<cmath>
 +
\[
 +
\sum_{i=n}^m \binom{i}{k} = \binom{m+1}{k+1} - \binom{n}{k+1} .
 +
\]
 +
</cmath>
 +
 +
Now, we use this result to solve this problem.
 +
 +
We have
 +
<cmath>
 +
\begin{align*}
 +
\sum_{i=3}^{40} \binom{\binom{i}{2}}{2}
 +
& = \sum_{i=3}^{40} \binom{\frac{i \left( i - 1 \right)}{2}}{2} \
 +
& = \sum_{i=3}^{40} \frac{\frac{i \left( i - 1 \right)}{2} \left( \frac{i \left( i - 1 \right)}{2}- 2 \right)}{2} \
 +
& = \frac{1}{8} \sum_{i=3}^{40}  \left( i \left( i - 1 \right) \left( i \left( i - 1 \right) - 1 \right) \right) \
 +
& = \frac{1}{8} \sum_{i=3}^{40}  \left( i \left( i - 1 \right)
 +
\left( \left( i - 2 \right) \left( i - 3 \right) + 4 \left( i - 2 \right)
 +
\right) \right) \
 +
& = 3 \left( \sum_{i=3}^{40} \binom{i}{4} + \sum_{i=3}^{40} \binom{i}{3} \right) \
 +
& = 3 \left( \binom{41}{5} - \binom{3}{5} + \binom{41}{4} - \binom{3}{4} \right) \
 +
& = 3 \left( \binom{41}{5} + \binom{41}{4} \right) \
 +
& = 3 \cdot \frac{41 \cdot 40 \cdot 39 \cdot 38}{5!} \left( 37 + 5 \right) \
 +
& = 3 \cdot 41 \cdot 13 \cdot 38 \cdot 42 \
 +
& = 38 \cdot 39 \cdot 41 \cdot 42 \
 +
& = \left( 40 - 2 \right) \left( 40 - 1 \right) \left( 40 + 1 \right) \left( 40 + 2 \right) \
 +
& = \left( 40^2 - 2^2 \right) \left( 40^2 - 1^2 \right) \
 +
& = \left( 40^2 - 4 \right) \left( 40^2 - 1 \right) \
 +
& = 40^4 - 40^2 \cdot 5 + 4  .
 +
\end{align*}
 +
</cmath>
 +
 +
Therefore, modulo 1000, <math>\sum_{i=3}^{40} \binom{\binom{i}{2}}{2}  \equiv \boxed{\textbf{(004) }}</math>.
 +
 +
~Steven Chen (www.professorchenedu.com)
  
 
==See Also==
 
==See Also==
 
{{AIME box|year=2022|n=II|num-b=9|num-a=11}}
 
{{AIME box|year=2022|n=II|num-b=9|num-a=11}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 11:58, 18 February 2022

Problem

Find the remainder when\[\binom{\binom{3}{2}}{2} + \binom{\binom{4}{2}}{2} + \dots +  \binom{\binom{40}{2}}{2}\]is divided by $1000$.

Solution

To solve this problem, we need to use the following result:

\[ \sum_{i=n}^m \binom{i}{k} = \binom{m+1}{k+1} - \binom{n}{k+1} . \]

Now, we use this result to solve this problem.

We have \begin{align*} \sum_{i=3}^{40} \binom{\binom{i}{2}}{2}  & = \sum_{i=3}^{40} \binom{\frac{i \left( i - 1 \right)}{2}}{2} \\ & = \sum_{i=3}^{40} \frac{\frac{i \left( i - 1 \right)}{2} \left( \frac{i \left( i - 1 \right)}{2}- 2 \right)}{2} \\ & = \frac{1}{8} \sum_{i=3}^{40}  \left( i \left( i - 1 \right) \left( i \left( i - 1 \right) - 1 \right) \right) \\ & = \frac{1}{8} \sum_{i=3}^{40}  \left( i \left( i - 1 \right)  \left( \left( i - 2 \right) \left( i - 3 \right) + 4 \left( i - 2 \right) \right) \right) \\ & = 3 \left( \sum_{i=3}^{40} \binom{i}{4} + \sum_{i=3}^{40} \binom{i}{3} \right) \\ & = 3 \left( \binom{41}{5} - \binom{3}{5} + \binom{41}{4} - \binom{3}{4} \right) \\ & = 3 \left( \binom{41}{5} + \binom{41}{4} \right) \\ & = 3 \cdot \frac{41 \cdot 40 \cdot 39 \cdot 38}{5!} \left( 37 + 5 \right) \\ & = 3 \cdot 41 \cdot 13 \cdot 38 \cdot 42 \\ & = 38 \cdot 39 \cdot 41 \cdot 42 \\ & = \left( 40 - 2 \right) \left( 40 - 1 \right) \left( 40 + 1 \right) \left( 40 + 2 \right) \\ & = \left( 40^2 - 2^2 \right) \left( 40^2 - 1^2 \right) \\ & = \left( 40^2 - 4 \right) \left( 40^2 - 1 \right) \\ & = 40^4 - 40^2 \cdot 5 + 4  . \end{align*}

Therefore, modulo 1000, $\sum_{i=3}^{40} \binom{\binom{i}{2}}{2}  \equiv \boxed{\textbf{(004) }}$.

~Steven Chen (www.professorchenedu.com)

See Also

2022 AIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 9
Followed by
Problem 11
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png