Difference between revisions of "2022 AIME II Problems/Problem 10"
Goatpotato (talk | contribs) m (→Solution 6 (Combinatorial Method)) |
m (index fix on sum) |
||
(18 intermediate revisions by 5 users not shown) | |||
Line 11: | Line 11: | ||
https://www.youtube.com/watch?v=4O1xiUYjnwE | https://www.youtube.com/watch?v=4O1xiUYjnwE | ||
− | ==Solution 1== | + | ==Solution 1 (Telescoping)== |
− | + | We first write the expression as a summation. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
<cmath> | <cmath> | ||
\begin{align*} | \begin{align*} | ||
Line 29: | Line 19: | ||
& = \sum_{i=3}^{40} \frac{\frac{i \left( i - 1 \right)}{2} \left( \frac{i \left( i - 1 \right)}{2}- 1 \right)}{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( i \left( i - 1 \right) - 2 \right) \\ | ||
− | & = \frac{1}{8} \sum_{i=3}^{40} | + | & = \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 \\ | & = 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 \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 - 2^2 \right) \left( 40^2 - 1^2 \right) \\ | ||
& = \left( 40^2 - 4 \right) \left( 40^2 - 1 \right) \\ | & = \left( 40^2 - 4 \right) \left( 40^2 - 1 \right) \\ | ||
− | & = 40^4 - 40^2 \cdot 5 + 4 | + | & = 40^4 - 40^2 \cdot 5 + 4 \\ |
+ | & \equiv \boxed{004}\pmod{1000}\ | ||
\end{align*} | \end{align*} | ||
</cmath> | </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)== | |
− | |||
− | |||
− | |||
− | ==Solution 2 ( | ||
Doing simple algebra calculation will give the following equation: | Doing simple algebra calculation will give the following equation: | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | \binom{\binom{n}{2}}{2} = \frac{\frac{n(n-1)}{2} \cdot (\frac{n(n-1)}{2}-1)}{2} | + | \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(n-1)(n^2-n-2)}{8}\\ |
− | \\ = \frac{(n+1)n(n-1)(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)!} | + | &= \frac{(n+1)!}{8\cdot (n-3)!} = 3 \cdot \frac{(n+1)!}{4!\cdot (n-3)!}\\ |
− | \\ = 3 \binom{n+1}{4} \end{align*} | + | &= 3 \binom{n+1}{4} \end{align*} |
</cmath> | </cmath> | ||
Next, by using [[Hockey-Stick Identity]], we have: | Next, by using [[Hockey-Stick Identity]], we have: | ||
− | <cmath>3 \cdot \sum_{i=3}^{40} \binom{ | + | <cmath>3 \cdot \sum_{i=3}^{40} \binom{i+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> | + | <cmath>=(40^2-2^2)(40^2-1^2) \equiv \boxed{004} ~(\text{mod}~ 1000)</cmath> |
− | |||
− | |||
==Solution 3== | ==Solution 3== | ||
Line 85: | Line 69: | ||
− | ==Solution 5 | + | ==Solution 5== |
+ | 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> | <cmath> | ||
\begin{align*} | \begin{align*} | ||
\sum_{i=3}^{40} \binom{\binom{i}{2}}{2} | \sum_{i=3}^{40} \binom{\binom{i}{2}}{2} | ||
− | & = \frac{1}{ | + | & = \sum_{i=3}^{40} \binom{\frac{i \left( i - 1 \right)}{2}}{2} \\ |
− | & = \frac{1}{ | + | & = \sum_{i=3}^{40} \frac{\frac{i \left( i - 1 \right)}{2} \left( \frac{i \left( i - 1 \right)}{2}- 1 \right)}{2} \\ |
− | & = \frac{38\ | + | & = \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*} | \end{align*} | ||
</cmath> | </cmath> | ||
− | |||
− | ~ | + | Therefore, modulo 1000, <math>\sum_{i=3}^{40} \binom{\binom{i}{2}}{2} \equiv \boxed{\textbf{(004) }}</math>. |
+ | |||
+ | ~Steven Chen (www.professorchenedu.com) | ||
==Solution 6 (Combinatorial Method)== | ==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 | + | 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>. |
− | To count this, note that each pair of <math>2</math> element subsets can either share <math>1</math> value | + | 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>. |
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>. | 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>. | ||
Line 110: | Line 118: | ||
<cmath> | <cmath> | ||
\begin{align*} | \begin{align*} | ||
− | \sum_{n=3}^{40} \binom{\binom{n}{2}}{2} &= \sum_{n=3}^{40} 3 \binom{n}{3} + 3 \binom{n}{4} \\ | + | \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( \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) | &= 3\left( \binom{41}{4} + \binom{41}{5} \right) |
Latest revision as of 23:11, 6 August 2024
Contents
Problem
Find the remainder whenis divided by
.
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.
is how we force the expression to telescope.
~qyang
Solution 2 (Hockey Stick)
Doing simple algebra calculation will give the following equation:
Next, by using Hockey-Stick Identity, we have:
Solution 3
Since 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
term:
,
,
,
,
, and
. Notice that these are just
,
,
,
,
,
. It's clear that this pattern continues up to
terms, noticing that the "indexing" starts with
instead of
. Thus, the value of the sum is
.
~A1001
Solution 4
As in solution 1, obtain Write this as
We can safely write this expression as , since plugging
and
into
both equal
meaning they won't contribute to the sum.
Use the sum of powers formulae. We obtain
We can factor the following expression as and simplifying, we have
Substituting and simplifying gets
so we would like to find
To do this, get
Next,
-sirswagger21
Solution 5
To solve this problem, we need to use the following result:
Now, we use this result to solve this problem.
We have
Therefore, modulo 1000, .
~Steven Chen (www.professorchenedu.com)
Solution 6 (Combinatorial Method)
We examine the expression . Imagine we have a set
of
integers. Then the expression can be translated to the number of pairs of
element subsets of
.
To count this, note that each pair of element subsets can either share
value or
values. In the former case, pick three integers
,
, and
. There are
ways to select these integers and
ways to pick which one of the three is the shared integer. This gives
.
In the latter case, we pick integers
,
,
, and
in a total of
ways. There are
ways to split this up into
sets of
integers —
ways to pick which
integers are together and dividing by
to prevent overcounting. This gives
.
So we have
We use the Hockey Stick Identity to evaluate this sum:
Evaluating while accounting for mod
gives the final answer to be
.
~ 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.