Difference between revisions of "2022 AMC 10B Problems/Problem 9"

(Solution 5(Combinatorics))
(Solution 5(Combinatorics))
Line 32: Line 32:
 
Suppose you are picking a permutation of <math>n</math> elements. Suppose that the correct order of the permutation is  
 
Suppose you are picking a permutation of <math>n</math> elements. Suppose that the correct order of the permutation is  
 
<cmath>x_1,x_2,x_3,\ldots,x_{2021},x_{2022}</cmath>
 
<cmath>x_1,x_2,x_3,\ldots,x_{2021},x_{2022}</cmath>
We want to find the probability of picking the permutation in the wrong order. Suppose that we have picked everything to the correct order except our last <math>2</math> elements. That is we have
+
We want to find the probability of picking the permutation in the wrong order. \\ Suppose that we have picked everything to the correct order except our last <math>2</math> elements. That is we have
 
<cmath>x_1,x_2,x_3,\ldots,x_{2019},x_{2020}</cmath>
 
<cmath>x_1,x_2,x_3,\ldots,x_{2019},x_{2020}</cmath>
We want pick the next element such that it does not equal to <math>x_{2021}</math>. There are <math>1</math> ways to choose that, so we add <math>\frac{1}{2!}</math> to the number. Suppose that we have picked everything to the correct order except our last <math>2</math> elements. That is we have
+
We want pick the next element such that it does not equal to <math>x_{2021}</math>. There are <math>1</math> ways to choose that, so we add <math>\frac{1}{2!}</math> to the number. \\ Suppose that we have picked everything to the correct order except our last <math>3</math> elements. That is we have
 
<cmath>x_1,x_2,x_3,\ldots,x_{2018},x_{2019}</cmath>
 
<cmath>x_1,x_2,x_3,\ldots,x_{2018},x_{2019}</cmath>
 
We want pick the next element such that it does not equal to <math>x_{2020}</math>. There are <math>2</math> ways to choose that, so we add <math>\frac{2}{3!}</math> to the number.  
 
We want pick the next element such that it does not equal to <math>x_{2020}</math>. There are <math>2</math> ways to choose that, so we add <math>\frac{2}{3!}</math> to the number.  

Revision as of 04:09, 22 November 2022

Problem

The sum \[\frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!}+\dots+\frac{2021}{2022!}\]can be expressed as $a-\frac{1}{b!}$, where $a$ and $b$ are positive integers. What is $a+b$?

$\textbf{(A)}\ 2020 \qquad\textbf{(B)}\ 2021 \qquad\textbf{(C)}\ 2022 \qquad\textbf{(D)}\ 2023 \qquad\textbf{(E)}\ 2024$

Solution 1

Note that $\frac{n}{(n+1)!} = \frac{1}{n!} - \frac{1}{(n+1)!}$, and therefore this sum is a telescoping sum, which is equivalent to $1 - \frac{1}{2022!}$. Our answer is $1 + 2022 = \boxed{\textbf{(D)}\ 2023}$.

~mathboy100

Solution 2

We have $\left(\frac{1}{2!}+\frac{2}{3!}+\dots+\frac{2021}{2022!}\right)+\frac{1}{2022!}=\left(\frac{1}{2!}+\frac{2}{3!}+\dots+\frac{2020}{2021!}\right)+\frac{1}{2021!}$ from canceling a 2022 from $\frac{2021+1}{2022!}$. This sum clearly telescopes, thus we end up with $\left(\frac{1}{2!}+\frac{2}{3!}\right)+\frac{1}{3!}=\frac{2}{2!}=1$. Thus the original equation is equal to $1-\frac{1}{2022}$, and $1+2022=2023$. $\boxed{\textbf{(D)}\ 2023}$.

~not_slay (+ minor LaTeX edit ~TaeKim)

Solution 3 (Induction)

By looking for a pattern, we see that $\tfrac{1}{2!} = 1 - \tfrac{1}{2!}$ and $\tfrac{1}{2!} + \tfrac{2}{3!} = \tfrac{5}{6} = 1 - \tfrac{1}{3!}$, so we can conclude by engineer's induction that the sum in the problem is equal to $1 - \tfrac{1}{2022!}$, for an answer of $\boxed{\textbf{(D)}\ 2023}$. This can be proven with actual induction as well; we have already established $2$ base cases, so now assume that $\tfrac{1}{2!} + \tfrac{2}{3!} + \cdots \tfrac{n-1}{n!} = 1 - \tfrac{1}{n!}$ for $n = k$. For $n = k + 1$ we get $\tfrac{1}{2!} + \tfrac{2}{3!} + \cdots \tfrac{n-1}{n!} + \tfrac{n}{(n+1)!} = 1 - \tfrac{1}{n!} + \tfrac{n}{(n+1)!} = 1 - \tfrac{n+1}{(n+1)!} + \tfrac{n}{(n+1)!} = 1 - \tfrac{1}{(n+1)!}$, completing the proof. ~eibc

Solution 4

Let $x=\left(\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\dots+\frac{1}{2022!}\right)$ \begin{align*} \left(\frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!}+\dots+\frac{2021}{2022!}\right)+\left(\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\dots+\frac{1}{2022!}\right)&=\left(\frac{1}{1!}+\frac{2}{2!}+\frac{3}{3!}+\dots+\frac{2022}{2022!}\right)\\ \left(\frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!}+\dots+\frac{2021}{2022!}\right)+x&=\left(\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\dots+\frac{1}{2021!}\right)\\ \left(\frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!}+\dots+\frac{2021}{2022!}\right)+x&=x+1-\frac{1}{2022!}\\ \left(\frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!}+\dots+\frac{2021}{2022!}\right)&=1-\frac{1}{2022!} \end{align*}~lopkiloinm

Solution 5(Combinatorics)

Suppose you are picking a permutation of $n$ elements. Suppose that the correct order of the permutation is \[x_1,x_2,x_3,\ldots,x_{2021},x_{2022}\] We want to find the probability of picking the permutation in the wrong order. \\ Suppose that we have picked everything to the correct order except our last $2$ elements. That is we have \[x_1,x_2,x_3,\ldots,x_{2019},x_{2020}\] We want pick the next element such that it does not equal to $x_{2021}$. There are $1$ ways to choose that, so we add $\frac{1}{2!}$ to the number. \\ Suppose that we have picked everything to the correct order except our last $3$ elements. That is we have \[x_1,x_2,x_3,\ldots,x_{2018},x_{2019}\] We want pick the next element such that it does not equal to $x_{2020}$. There are $2$ ways to choose that, so we add $\frac{2}{3!}$ to the number. ~lopkiloinm

Video Solution

https://youtu.be/4vdVGYXGvzg

- Whiz

See Also

2022 AMC 10B (ProblemsAnswer KeyResources)
Preceded by
Problem 8
Followed by
Problem 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
All AMC 10 Problems and Solutions

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