Difference between revisions of "2021 Fall AMC 12B Problems/Problem 23"
R00tsofunity (talk | contribs) |
|||
(19 intermediate revisions by 6 users not shown) | |||
Line 6: | Line 6: | ||
==Solution 1== | ==Solution 1== | ||
− | There are <math>29</math> possible pairs of consecutive integers, namely <math>\{1,2\}, \{ | + | There are <math>29</math> possible pairs of consecutive integers, namely <math>p_1=\{1,2\}, \cdots, p_{29}=\{29,30\}</math>. |
+ | Define a random variable <math>X_i</math>, with <math>X_i=1</math>, if <math>p_i</math> is part of the 5-element subset, and <math>0</math> otherwise. | ||
+ | Then the number of pairs of consecutive integers in a <math>5</math>-element selection is given by the sum <math>X_1+\cdots + X_{29}</math>. By linearity of expectation, the expected value is equal to the sum of the <math>\mathbb{E}[X_i]</math>: | ||
+ | <cmath>\mathbb{E}[X_1+\cdots +X_{29}]=\mathbb{E}[X_1]+\cdots + \mathbb{E}[X_{29}]</cmath> | ||
+ | To compute <math>\mathbb{E}[X_i]</math>, note that <math>X_i=1</math> for a total of <math>_{28}C_3</math> out of <math>_{30}C_5</math> possible selections. Thus<cmath>\mathbb{E}[X_i]=\frac{\binom{28}{3}}{\binom{30}{5}}= \frac 1{29}\cdot \frac 23, \quad \textrm{which implies} \quad \mathbb{E}[X_1+\cdots +X_{29}]= \boxed{\textbf{(A)}\ \frac{2}{3}}.</cmath> | ||
+ | ~kingofpineapplz | ||
− | + | ==Solution 2== | |
+ | Alternatively, using linearity of expectation on the chosen subset: there are <math>{5 \choose 2}</math> pairs of integers. There are 29 pairs of consecutive integers out of <math>{30 \choose 2}</math> possible pairs, thus the probability that any given pair is consecutive is <math>\frac{29}{{30 \choose 2}}</math>. By linearity of expectation, there are <math>\frac{{5 \choose 2}29}{{30 \choose 2}} = \frac{10 \cdot 29}{\frac{30 \cdot 29}{2}} = \boxed{\textbf{(A)}\ \frac{2}{3}}</math> such pairs on average. | ||
− | + | ~MT | |
+ | ==Solution 3 (casework bash)== | ||
− | + | We will proceed with some casework. | |
+ | Let <math>n</math> be the number of sets of consecutive numbers in the subset. | ||
+ | Note that the maximum possible value of <math>n</math> is <math>4.</math> | ||
+ | Case <math>1</math>: <math>n = 4</math> | ||
+ | There is only one way to arrange the distribution of the number of elements in each block here. There are <math>\dbinom{26}{1} = 26</math> ways to arrange where that block of <math>5</math> numbers will go, so a total of <math>1 \cdot 26 = 26</math> ways for this case. | ||
+ | Case <math>2</math>: <math>n = 3</math> | ||
+ | There are <math>4</math> ways to arrange the distribution of the number of elements in each block here. (4-1, 3-2, 2-3, 1-4). There are <math>\dbinom{26}{2}</math> ways to arrange where those two blocks of numbers go among the other numbers such that no two of those blocks are adjacent to each other. Total for this case: <math>4 \cdot 325 = 1300.</math> | ||
+ | Case <math>3</math>: <math>n = 2</math> | ||
+ | By Stars and Bars, there are <math>\dbinom{4}{2} = 6</math> ways to arrange the distribution of the number of elements in each block here. There are <math>\dbinom{26}{3}</math> ways to arrange where those three blocks of numbers go among the other numbers such that no two of those blocks are adjacent to each other. Total for this case: <math>6 \cdot 2600 = 15600.</math> | ||
+ | Case <math>4</math>: <math>n = 1</math> | ||
+ | By Stars and Bars, there are <math>\dbinom{4}{3} = 4</math> ways to arrange the distribution of the number of elements in each block here. There are <math>\dbinom{26}{4}</math> ways to arrange where those four blocks of numbers go among the other numbers such that no two of those blocks are adjacent to each other. Total for this case: <math>4 \cdot 14950 = 59800.</math> | ||
+ | Since the last case <math>n=0</math> doesn't contribute to the expected value sum, we can ignore it. | ||
+ | Using the expected value formula, our desired value is <cmath>\frac{4 \cdot 26 + 3 \cdot 1300 + 2 \cdot 15600 + 1 \cdot 59800}{\tbinom{30}{5}} = \frac{95004}{142506} = \boxed{\frac{2}{3}}.</cmath> | ||
− | + | -fidgetboss_4000 | |
− | + | == Solution 4 == | |
− | |||
− | == Solution | ||
We define an outcome as <math>\left( a_1 ,\cdots, a_5 \right)</math> with <math>1 \leq a_1 < a_2 < a_3 < a_4 < a_5 \leq 30</math>. | We define an outcome as <math>\left( a_1 ,\cdots, a_5 \right)</math> with <math>1 \leq a_1 < a_2 < a_3 < a_4 < a_5 \leq 30</math>. | ||
Line 364: | Line 381: | ||
Therefore, the answer is <math>\boxed{\textbf{(A) }\frac{2}{3}}</math>. | Therefore, the answer is <math>\boxed{\textbf{(A) }\frac{2}{3}}</math>. | ||
− | |||
− | + | ~Steven Chen (www.professorchenedu.com) | |
− | Let <math> | + | |
− | + | ==Solution 5== | |
− | + | Let <math>a_1, a_2, a_3, a_4, a_5</math> be the five numbers chosen. Then, we can consider the first number and the four differences, <math>a_1, a_2-a_1, a_3-a_2, a_4-a_3, a_5-a_4</math>. Now, each must be positive integers and the sum is less than or equal to <math>30</math>, which there are <math>\binom{30}{5}</math> by Hockey-Stick Identity. Now, we can use the Linearity of Expectation on <math>a_2-a_1, a_3-a_2, a_4-a_3, a_5-a_4</math> since each of them being <math>1</math> represents a pair of consecutive integer. For each of them, we have <math>\binom{28}{3}+\binom{27}{3}+...+1=\binom{29}{4}</math>. Now, we have four such numbers to consider, and by Linearity of Expectation, its <math>4\cdot \binom{29}{4}</math>. Now, we divide by <math>\binom{30}{5}</math> to get the answer of <math>\boxed{\textbf{(A)} ~\frac{2}{3}}</math>. | |
− | + | ||
− | + | ~Hayabusa1 | |
− | + | ||
− | + | == Video Solution by OmegaLearn == | |
− | + | https://youtu.be/EE-TtptBHeI?t=541 | |
− | + | ||
− | + | ~ pi_is_3.14 | |
− | + | ||
− | + | ==Video Solution== | |
+ | https://youtu.be/OH5H-ic8Pgw | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
− | + | ==Video Solution by The Power Of Logic== | |
− | + | https://youtu.be/hgsPW2sM1GQ | |
==See Also== | ==See Also== | ||
{{AMC12 box|year=2021 Fall|ab=B|num-b=22|num-a=24}} | {{AMC12 box|year=2021 Fall|ab=B|num-b=22|num-a=24}} | ||
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 00:38, 6 January 2023
Contents
Problem
What is the average number of pairs of consecutive integers in a randomly selected subset of distinct integers chosen from the set
? (For example the set
has
pairs of consecutive integers.)
Solution 1
There are possible pairs of consecutive integers, namely
.
Define a random variable
, with
, if
is part of the 5-element subset, and
otherwise.
Then the number of pairs of consecutive integers in a
-element selection is given by the sum
. By linearity of expectation, the expected value is equal to the sum of the
:
To compute
, note that
for a total of
out of
possible selections. Thus
~kingofpineapplz
Solution 2
Alternatively, using linearity of expectation on the chosen subset: there are pairs of integers. There are 29 pairs of consecutive integers out of
possible pairs, thus the probability that any given pair is consecutive is
. By linearity of expectation, there are
such pairs on average.
~MT
Solution 3 (casework bash)
We will proceed with some casework.
Let be the number of sets of consecutive numbers in the subset.
Note that the maximum possible value of
is
Case
:
There is only one way to arrange the distribution of the number of elements in each block here. There are
ways to arrange where that block of
numbers will go, so a total of
ways for this case.
Case
:
There are
ways to arrange the distribution of the number of elements in each block here. (4-1, 3-2, 2-3, 1-4). There are
ways to arrange where those two blocks of numbers go among the other numbers such that no two of those blocks are adjacent to each other. Total for this case:
Case
:
By Stars and Bars, there are
ways to arrange the distribution of the number of elements in each block here. There are
ways to arrange where those three blocks of numbers go among the other numbers such that no two of those blocks are adjacent to each other. Total for this case:
Case
:
By Stars and Bars, there are
ways to arrange the distribution of the number of elements in each block here. There are
ways to arrange where those four blocks of numbers go among the other numbers such that no two of those blocks are adjacent to each other. Total for this case:
Since the last case
doesn't contribute to the expected value sum, we can ignore it.
Using the expected value formula, our desired value is
-fidgetboss_4000
Solution 4
We define an outcome as with
.
We denote by the sample space. Hence.
.
: There is only 1 pair of consecutive integers.
:
is the single pair of consecutive integers.
We denote by the collection of outcomes satisfying this condition.
Hence,
is the number of outcomes satisfying
Denote ,
,
,
,
.
Hence,
is the number of outcomes satisfying
Therefore, .
:
is the single pair of consecutive integers.
We denote by the collection of outcomes satisfying this condition.
Hence,
is the number of outcomes satisfying
Similar to our analysis for Case 1.1, .
:
is the single pair of consecutive integers.
We denote by the collection of outcomes satisfying this condition.
Hence,
is the number of outcomes satisfying
Similar to our analysis for Case 1.1, .
:
is the single pair of consecutive integers.
We denote by the collection of outcomes satisfying this condition.
Hence,
is the number of outcomes satisfying
Similar to our analysis for Case 1.1, .
: There are 2 pairs of consecutive integers.
:
and
are two pairs of consecutive integers.
We denote by the collection of outcomes satisfying this condition.
Hence,
is the number of outcomes satisfying
Similar to our analysis for Case 1.1, .
:
and
are two pairs of consecutive integers.
We denote by the collection of outcomes satisfying this condition.
Hence,
is the number of outcomes satisfying
Similar to our analysis for Case 1.1, .
:
and
are two pairs of consecutive integers.
We denote by the collection of outcomes satisfying this condition.
Hence,
is the number of outcomes satisfying
Similar to our analysis for Case 1.1, .
:
and
are two pairs of consecutive integers.
We denote by the collection of outcomes satisfying this condition.
Hence,
is the number of outcomes satisfying
Similar to our analysis for Case 1.1, .
:
and
are two pairs of consecutive integers.
We denote by the collection of outcomes satisfying this condition.
Hence,
is the number of outcomes satisfying
Similar to our analysis for Case 1.1, .
:
and
are two pairs of consecutive integers.
We denote by the collection of outcomes satisfying this condition.
Hence,
is the number of outcomes satisfying
Similar to our analysis for Case 1.1, .
: There are 3 pairs of consecutive integers.
:
,
and
are three pairs of consecutive integers.
We denote by the collection of outcomes satisfying this condition.
Hence,
is the number of outcomes satisfying
Similar to our analysis for Case 1.1, .
:
,
and
are three pairs of consecutive integers.
We denote by the collection of outcomes satisfying this condition.
Hence,
is the number of outcomes satisfying
Similar to our analysis for Case 1.1, .
:
,
and
are three pairs of consecutive integers.
We denote by the collection of outcomes satisfying this condition.
Hence,
is the number of outcomes satisfying
Similar to our analysis for Case 1.1, .
:
,
and
are three pairs of consecutive integers.
We denote by the collection of outcomes satisfying this condition.
Hence,
is the number of outcomes satisfying
Similar to our analysis for Case 1.1, .
: There are 4 pairs of consecutive integers.
In this case, are consecutive integers.
We denote by the collection of outcomes satisfying this condition.
Hence,
is the number of outcomes satisfying
Hence, .
Therefore, the average number of pairs of consecutive integers is
Therefore, the answer is .
~Steven Chen (www.professorchenedu.com)
Solution 5
Let be the five numbers chosen. Then, we can consider the first number and the four differences,
. Now, each must be positive integers and the sum is less than or equal to
, which there are
by Hockey-Stick Identity. Now, we can use the Linearity of Expectation on
since each of them being
represents a pair of consecutive integer. For each of them, we have
. Now, we have four such numbers to consider, and by Linearity of Expectation, its
. Now, we divide by
to get the answer of
.
~Hayabusa1
Video Solution by OmegaLearn
https://youtu.be/EE-TtptBHeI?t=541
~ pi_is_3.14
Video Solution
~MathProblemSolvingSkills.com
Video Solution by The Power Of Logic
See Also
2021 Fall AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 22 |
Followed by Problem 24 |
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 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.