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

Line 60: Line 60:
  
 
~DSAERF-CALMIT (https://binaryphi.site)
 
~DSAERF-CALMIT (https://binaryphi.site)
 
==Solution 3==
 
It is somewhat well know that <math>{{n \choose 2} \choose 2} = 3 {n+1 \choose 4}</math>. (In particular, this is exercise 12.3.1 in AoPS Intermediate Counting and Probability book.)
 
 
With this in mind, we can substitute out each term in the expression:
 
<cmath>
 
\begin{align*}
 
& {{3 \choose 2} \choose 2} + {{4 \choose 2} \choose 2} + \dots + {{40 \choose 2} \choose 2} \
 
= ~ & 3\left( {4 \choose 4} + {5 \choose 4} + \dots + {41 \choose 4} \right) \
 
= ~ & 3 {42 \choose 5}.
 
\end{align*}
 
</cmath>
 
We must find the remainder when this is divided by <math>1000</math>. There is no clever method: there is only bash.
 
<cmath>
 
\begin{align*}
 
& 3 {42 \choose 5} \
 
= ~ & \frac{42 \cdot 41 \cdot 40 \cdot 39 \cdot 38}{5 \cdot 4 \cdot 2} \
 
= ~ & 42 \cdot 41 \cdot 39 \cdot 38 \
 
= ~ & (40-2)(40+2)(40-1)(40+1) \
 
= ~ & (40^2-4)(40^2-1) \
 
= ~ & 40^4 - 5 \cdot 40^2 + 4.
 
\end{align*}
 
</cmath>
 
The first two terms of this are divisible by <math>1000</math>, so the remainder when the whole thing is divided by <math>1000</math> is just <math>\boxed{004}</math>.
 
  
 
==Solution 4==
 
==Solution 4==

Revision as of 19:02, 21 April 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$.

Video solution

https://www.youtube.com/watch?v=4O1xiUYjnwE

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}- 1 \right)}{2} \\ & = \frac{1}{8} \sum_{i=3}^{40}  i \left( i - 1 \right) \left( i \left( i - 1 \right) - 2 \right)  \\ & = \frac{1}{8} \sum_{i=3}^{40}  i \left( i - 1 \right)  \left( \left( i - 2 \right) \left( i - 3 \right) + 4 \left( i - 2 \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)

Solution 2 (similar to solution 1)

Doing simple algebra calculation will give the following equation: \begin{align*} \binom{\binom{n}{2}}{2} = \frac{\frac{n(n-1)}{2} \cdot (\frac{n(n-1)}{2}-1)}{2} \\ = \frac{n(n-1)(n^2-n-2)}{8} \\ = \frac{(n+1)n(n-1)(n-2)}{8} \\ = \frac{(n+1)!}{8\cdot (n-3)!} = 3 \cdot \frac{(n+1)!}{4!\cdot (n-3)!} \\ = 3 \binom{n+1}{4} \end{align*}

Next, by using Hockey-Stick Identity, we have: \[3 \cdot \sum_{i=3}^{40} \binom{n+1}{4} = 3 \binom{42}{5} = 42 \cdot 41 \cdot 39 \cdot 38\] \[=(40^2-2^2)(40^2-1^2) \equiv \boxed{004} (mod 1000)\]

~DSAERF-CALMIT (https://binaryphi.site)

Solution 4

Since $40$ seems like a completely arbitrary number, we can use Engineer's Induction by listing out the first few sums. These are, in the order of how many terms there are starting from $1$ term: $3$, $18$, $63$, $168$, $378$, and $756$. Notice that these are just $3 \cdot \dbinom50$, $3 \cdot \dbinom61$, $3 \cdot \dbinom72$, $3 \cdot \dbinom83$, $3 \cdot \dbinom94$, $3 \cdot \dbinom{10}5$. It's clear that this pattern continues up to $38$ terms, noticing that the "indexing" starts with $\dbinom32$ instead of $\dbinom12$. Thus, the value of the sum is $3 \cdot \dbinom{42}{37}=2552004 \equiv \boxed{\textbf{004}} \pmod{1000}$.

~A1001

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