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

Revision as of 11:28, 22 June 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 1

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 3

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

Solution 4

As in solution 1, obtain $\sum_{i=3}^{40} \binom{\binom{i}{2}}{2} = \frac{1}{8} \sum_{i=3}^{40} i^4-2i^3-i^2+2i.$ Write this as $\frac{1}{8}\left(\sum_{i=3}^{40} i^4 - 2\sum_{i=3}^{40}i^3 - \sum_{i=3}^{40}i^2 + 2\sum_{i=3}^{40}i\right).$

We can safely write this expression as $\frac{1}{8}\left(\sum_{i=1}^{40} i^4 - 2\sum_{i=1}^{40}i^3 - \sum_{i=1}^{40}i^2 + 2\sum_{i=1}^{40}i\right)$ , since plugging $i=1$ and $i=2$ into $i^4-2i^3-i^2+2i$ both equal $0,$ meaning they won't contribute to the sum.

Use the sum of powers formulae. We obtain $\frac{1}{8}\left(\frac{i(i+1)(2i+1)(3i^2+3i-1)}{30} - \frac{i^2(i+1)^2}{2} - \frac{i(i+1)(2i+1)}{6} + i(i+1)\right) \text{ where i = 40.}$

We can factor the following expression as $\frac{1}{8}\left(\frac{i(i+1)(2i+1)(3i^2+3i-6)}{30} - \frac{i(i+1)}{2} (i(i+1)-2)\right),$ and simplifying, we have $\sum_{i=3}^{40} \binom{\binom{i}{2}}{2} = \frac{i(i+1)(2i+1)(i^2+i-2)}{80}-\frac{i^2(i+1)^2-2i(i+1)}{16} \text{ where i = 40.}$

Substituting $i=40$ and simplifying gets $41\cdot 81\cdot 819 - 5\cdot 41\cdot 819,$ so we would like to find $819\cdot 76\cdot 41 \pmod{1000}.$ To do this, get $819\cdot 76\equiv 244 \pmod{1000}.$ Next, $244\cdot 41 \equiv \boxed{004} \pmod{1000}.$

-sirswagger21

@@ Line 65: / Line 65: @@
 ~A1001
+==Solution 4==
+As in solution 1, obtain <math>\sum_{i=3}^{40} \binom{\binom{i}{2}}{2} = \frac{1}{8} \sum_{i=3}^{40} i^4-2i^3-i^2+2i.</math> Write this as <cmath>\frac{1}{8}\left(\sum_{i=3}^{40} i^4 - 2\sum_{i=3}^{40}i^3 - \sum_{i=3}^{40}i^2 + 2\sum_{i=3}^{40}i\right).</cmath>
+We can safely write this expression as <math>\frac{1}{8}\left(\sum_{i=1}^{40} i^4 - 2\sum_{i=1}^{40}i^3 - \sum_{i=1}^{40}i^2 + 2\sum_{i=1}^{40}i\right)</math>, since plugging <math>i=1</math> and <math>i=2</math> into <math>i^4-2i^3-i^2+2i</math> both equal <math>0,</math> meaning they won't contribute to the sum.
+Use the sum of powers formulae. We obtain <cmath>\frac{1}{8}\left(\frac{i(i+1)(2i+1)(3i^2+3i-1)}{30} - \frac{i^2(i+1)^2}{2} - \frac{i(i+1)(2i+1)}{6} + i(i+1)\right) \text{ where i = 40.}</cmath>
+We can factor the following expression as <math>\frac{1}{8}\left(\frac{i(i+1)(2i+1)(3i^2+3i-6)}{30} - \frac{i(i+1)}{2} (i(i+1)-2)\right),</math> and simplifying, we have <cmath>\sum_{i=3}^{40} \binom{\binom{i}{2}}{2} = \frac{i(i+1)(2i+1)(i^2+i-2)}{80}-\frac{i^2(i+1)^2-2i(i+1)}{16} \text{ where i = 40.}</cmath>
+Substituting <math>i=40</math> and simplifying gets <math>41\cdot 81\cdot 819 - 5\cdot 41\cdot 819,</math> so we would like to find <math>819\cdot 76\cdot 41 \pmod{1000}.</math> To do this, get <math>819\cdot 76\equiv 244 \pmod{1000}.</math> Next, <math>244\cdot 41 \equiv \boxed{004} \pmod{1000}.</math>
+-sirswagger21
 ==See Also==
 {{AIME box|year=2022|n=II|num-b=9|num-a=11}}
 {{MAA Notice}}

2022 AIME II (Problems • Answer Key • Resources)
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

Page

Toolbox

Search