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 "2022 AIME II Problems/Problem 10"
m (Solution 6 - added brackets)
 
(26 intermediate revisions by 9 users not shown)
Line 2: Line 2:
  
 
Find the remainder when<cmath>\binom{\binom{3}{2}}{2} + \binom{\binom{4}{2}}{2} + \dots +  \binom{\binom{40}{2}}{2}</cmath>is divided by <math>1000</math>.
 
Find the remainder when<cmath>\binom{\binom{3}{2}}{2} + \binom{\binom{4}{2}}{2} + \dots +  \binom{\binom{40}{2}}{2}</cmath>is divided by <math>1000</math>.
 +
 +
== Video Solution by OmegaLearn ==
 +
https://youtu.be/pGkLAX381_s?t=1035
 +
 +
~ pi_is_3.14
  
 
==Video solution==
 
==Video solution==
 
https://www.youtube.com/watch?v=4O1xiUYjnwE
 
https://www.youtube.com/watch?v=4O1xiUYjnwE
  
−
==Solution==
+
==Solution 1 (Telescoping)==
 +
We first write the expression as a summation.
 +
<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}- 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(i - 1)(i^2-i-2) \\
 +
& = \frac{1}{8} \sum_{i=3}^{40} i(i-1)(i+1)(i-2) \\
 +
& = \frac{1}{8}\sum_{i=3}^{40} (i-2)(i-1)i(i+1) \\
 +
& = \frac{1}{40}\sum_{i=3}^{40}[(i-2)(i-1)i(i+1)(i+2)-(i-3)(i-2)(i-1)i(i+1)]* \\
 +
& = \frac{38\cdot39\cdot40\cdot41\cdot42-0}{40}\\
 +
& = 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 \\
 +
& \equiv \boxed{004}\pmod{1000}\
 +
\end{align*}
 +
</cmath>
 +
<math>*(i-2)(i-1)i(i+1)=\frac{1}{5}[(i-2)(i-1)i(i+1)(i+2)-(i-3)(i-2)(i-1)i(i+1)]</math> is how we force the expression to telescope.
 +
~qyang
 +
 
 +
==Solution 2 (Hockey Stick)==
 +
 
 +
Doing simple algebra calculation will give the following equation:
 +
<cmath>\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*}
 +
</cmath>
 +
 
 +
Next, by using [[Hockey-Stick Identity]], we have:
 +
<cmath>3 \cdot \sum_{i=3}^{40} \binom{n+1}{4} = 3 \binom{42}{5} = 42 \cdot 41 \cdot 39 \cdot 38</cmath>
 +
<cmath>=(40^2-2^2)(40^2-1^2) \equiv \boxed{004} ~(\text{mod}~ 1000)</cmath>
 +
 
 +
==Solution 3==
 +
Since <math>40</math> 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 <math>1</math> term: <math>3</math>, <math>18</math>, <math>63</math>, <math>168</math>, <math>378</math>, and <math>756</math>. Notice that these are just <math>3 \cdot \dbinom50</math>, <math>3 \cdot \dbinom61</math>, <math>3 \cdot \dbinom72</math>, <math>3 \cdot \dbinom83</math>, <math>3 \cdot \dbinom94</math>, <math>3 \cdot \dbinom{10}5</math>. It's clear that this pattern continues up to <math>38</math> terms, noticing that the "indexing" starts with <math>\dbinom32</math> instead of <math>\dbinom12</math>. Thus, the value of the sum is <math>3 \cdot \dbinom{42}{37}=2552004 \equiv \boxed{\textbf{004}} \pmod{1000}</math>.
 +
 
 +
~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
 +
 
 +
 
 +
==Solution 5==
 
To solve this problem, we need to use the following result:
 
To solve this problem, we need to use the following result:
  
Line 44: Line 107:
 
~Steven Chen (www.professorchenedu.com)
 
~Steven Chen (www.professorchenedu.com)
  
−
==Solution 2 (similar to solution 1)==
+
==Solution 6 (Combinatorial Method)==
−
 
+
We examine the expression <math>\binom{\binom{n}{2}}{2}</math>. Imagine we have a set <math>S</math> of <math>n</math> integers. Then the expression can be translated to the number of pairs of <math>2</math> element subsets of <math>S</math>.
−
Doing simple algebra calculation will give the following equation:
 
−
<cmath>\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*}
 
−
</cmath>
 
−
 
 
−
Next, by using [[Hockey-Stick Identity]], we have:
 
−
<cmath>3 \cdot \sum_{i=3}^{40} \binom{n+1}{4} = 3 \binom{42}{5} = 42 \cdot 41 \cdot 39 \cdot 38</cmath>
 
−
<cmath>=(40^2-2^2)(40^2-1^2) \equiv \boxed{004} (mod 1000)</cmath>
 
  
−
~DSAERF-CALMIT (https://binaryphi.site)
+
To count this, note that each pair of <math>2</math> element subsets can either share <math>1</math> value or <math>0</math> values. In the former case, pick three integers <math>a</math>, <math>b</math>, and <math>c</math>. There are <math>\binom{n}{3}</math> ways to select these integers and <math>3</math> ways to pick which one of the three is the shared integer. This gives <math>3\cdot \binom{n}{3}</math>.
  
−
==Solution 3==
+
In the latter case, we pick <math>4</math> integers <math>a</math>, <math>b</math>, <math>c</math>, and <math>d</math> in a total of <math>\binom{n}{4}</math> ways. There are <math>\frac{1}{2}\binom{4}{2} = 3</math> ways to split this up into <math>2</math> sets of <math>2</math> integers — <math>\binom{4}{2}</math> ways to pick which <math>2</math> integers are together and dividing by <math>2</math> to prevent overcounting. This gives <math>3\cdot \binom{n}{4}</math>.
−
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:
+
So we have <cmath>\binom{\binom{n}{2}}{2} = 3\cdot \binom{n}{3} + 3\cdot \binom{n}{4}</cmath>
 +
We use the Hockey Stick Identity to evaluate this sum:
 
<cmath>
 
<cmath>
 
\begin{align*}
 
\begin{align*}
−
& {{3 \choose 2} \choose 2} + {{4 \choose 2} \choose 2} + \dots + {{40 \choose 2} \choose 2} \\
+
\sum_{n=3}^{40} \binom{\binom{n}{2}}{2} &= \sum_{n=3}^{40} \left( 3 \binom{n}{3} + 3 \binom{n}{4} \right) \\
−
= ~ & 3\left( {4 \choose 4} + {5 \choose 4} + \dots + {41 \choose 4} \right) \\
+
&= 3 \left( \sum_{n=3}^{40}  \binom{n}{3} \right) + 3\left( \sum_{n=4}^{40}  \binom{n}{4} \right) \\
−
= ~ & 3 {42 \choose 5}.
+
&= 3\left( \binom{41}{4} + \binom{41}{5} \right)
 
\end{align*}
 
\end{align*}
 
</cmath>
 
</cmath>
−
We must find the remainder when this is divided by <math>1000</math>. There is no clever method: there is only bash.
+
Evaluating while accounting for mod <math>1000</math> gives the final answer to be <math>\boxed{004}</math>.
−
<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==
 
−
Since <math>40</math> 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 <math>1</math> term: <math>3</math>, <math>18</math>, <math>63</math>, <math>168</math>, <math>378</math>, and <math>756</math>. Notice that these are just <math>3 \cdot \dbinom50</math>, <math>3 \cdot \dbinom61</math>, <math>3 \cdot \dbinom72</math>, <math>3 \cdot \dbinom83</math>, <math>3 \cdot \dbinom94</math>, <math>3 \cdot \dbinom{10}5</math>. It's clear that this pattern continues up to <math>38</math> terms, noticing that the "indexing" starts with <math>\dbinom32</math> instead of <math>\dbinom12</math>. Thus, the value of the sum is <math>3 \cdot \dbinom{42}{37}=2552004 \equiv \boxed{\textbf{004}} \pmod{1000}</math>.
 
  
−
~A1001
+
~ GoatPotato
  
 
==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}}

Latest revision as of 23:31, 30 January 2024

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 by OmegaLearn

https://youtu.be/pGkLAX381_s?t=1035

~ pi_is_3.14

Video solution

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

Solution 1 (Telescoping)

We first write the expression as a summation. \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(i - 1)(i^2-i-2) \\ & = \frac{1}{8} \sum_{i=3}^{40} i(i-1)(i+1)(i-2) \\ & = \frac{1}{8}\sum_{i=3}^{40} (i-2)(i-1)i(i+1) \\ & = \frac{1}{40}\sum_{i=3}^{40}[(i-2)(i-1)i(i+1)(i+2)-(i-3)(i-2)(i-1)i(i+1)]* \\ & = \frac{38\cdot39\cdot40\cdot41\cdot42-0}{40}\\ & = 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 \\ & \equiv \boxed{004}\pmod{1000}\ \end{align*} $*(i-2)(i-1)i(i+1)=\frac{1}{5}[(i-2)(i-1)i(i+1)(i+2)-(i-3)(i-2)(i-1)i(i+1)]$ is how we force the expression to telescope. ~qyang

Solution 2 (Hockey Stick)

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} ~(\text{mod}~ 1000)\]

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


Solution 5

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 6 (Combinatorial Method)

We examine the expression $\binom{\binom{n}{2}}{2}$. Imagine we have a set $S$ of $n$ integers. Then the expression can be translated to the number of pairs of $2$ element subsets of $S$.

To count this, note that each pair of $2$ element subsets can either share $1$ value or $0$ values. In the former case, pick three integers $a$, $b$, and $c$. There are $\binom{n}{3}$ ways to select these integers and $3$ ways to pick which one of the three is the shared integer. This gives $3\cdot \binom{n}{3}$.

In the latter case, we pick $4$ integers $a$, $b$, $c$, and $d$ in a total of $\binom{n}{4}$ ways. There are $\frac{1}{2}\binom{4}{2} = 3$ ways to split this up into $2$ sets of $2$ integers — $\binom{4}{2}$ ways to pick which $2$ integers are together and dividing by $2$ to prevent overcounting. This gives $3\cdot \binom{n}{4}$.

So we have \[\binom{\binom{n}{2}}{2} = 3\cdot \binom{n}{3} + 3\cdot \binom{n}{4}\] We use the Hockey Stick Identity to evaluate this sum: \begin{align*} \sum_{n=3}^{40} \binom{\binom{n}{2}}{2} &= \sum_{n=3}^{40} \left( 3 \binom{n}{3} + 3 \binom{n}{4} \right) \\ &= 3 \left( \sum_{n=3}^{40} \binom{n}{3} \right) + 3\left( \sum_{n=4}^{40} \binom{n}{4} \right) \\ &= 3\left( \binom{41}{4} + \binom{41}{5} \right) \end{align*} Evaluating while accounting for mod $1000$ gives the final answer to be $\boxed{004}$.

~ GoatPotato

See Also

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

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=2022_AIME_II_Problems/Problem_10&oldid=213875"