Difference between revisions of "2025 SSMO Speed Round Problems/Problem 8"

Latest revision as of 17:14, 12 September 2025

Problem

Let $S$ be the set of all ordered pairs $(P,Q),$ where $P$ and $Q$ are subsets of $\{1,2,\dots, 25\}$ satisfying $|P\cup Q| = 17$ and $|(P\cap Q)\cap \{20,25\}|\ge 1$ . If an ordered pair $(A,B)$ is chosen randomly from $S,$ the expected value of $|A\cap B|$ is $\tfrac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m+n$ .

Solution

For each $i\in \{1,2,\dots, 25\}$ , let $p_i$ denote the probability that $i \in A\cap B$ , where $(A,B)$ is a randomly chosen element of $S$ . By the linearity of expected value, \begin{align*} \mathbb{E}[|A\cap B|] &= \mathbb{E}[p_1] + \mathbb{E}[p_2] + \cdots + \mathbb{E}[p_{25}] \\ &= p_1 + p_2 + \cdots + p_{25}. \end{align*} (Because the value of each $p_i$ is fixed, we have substituted $\mathbb{E}[p_i] = p_i$ .) By symmetry, $p_i = p_1$ for all valid $i$ not equal to $20$ or $25$ , and by symmetry again, $p_{25} = p_{20}$ . Therefore, $\mathbb{E}[|A\cap B|] = 23\cdot p_1 + 2\cdot p_{20}$ .

Our goal now is to find the values of $p_1$ and $p_{20}$ . We do this via casework on the three ways the condition $|(A\cap B)\cap \{20,25\}|\ge 1$ can be met. We will compute the values of $p_1$ and $p_{20}$ in each case, as well as finding the number of ordered pairs $(A,B)$ that fall under each case. The latter information will allow us to compute the probability that any given $(A,B)$ falls under each of the three cases, which in turn will let us compute $p_1$ and $p_{20}$ .

Case 1: both elements of $\{20,25\}$ lie in both $A$ and $B$ . Because $20, 25 \in A,B$ , we have $20, 25 \in A\cup B$ . We know that $|A\cup B| = 17$ , so we can choose the other $15$ elements of $|A\cup B|$ in $\tbinom{23}{15}$ ways. There are $3$ ways to assign each of these $15$ elements to $A$ and $B$ ; the element must lie in at least one of $A$ and $B$ , so it can lie in $A$ but not in $B$ , in $B$ but not in $A$ , or in both $A$ and $B$ . Therefore, there are $3^{15}\cdot\tbinom{23}{15}$ ordered pairs $(A,B)$ in this case.

To find $p_1$ in this case, observe that since each of the $23$ elements of $\{1,2,\dots, 25\}$ that are not $20$ or $25$ has an equal probability of being selected as an element of $A\cup B$ , the probability that $1 \in A\cup B$ is $\tfrac{15}{23}$ . If $1\in A\cup B$ , there is a $\tfrac{1}{3}$ probability that $1 \in A\cap B$ , so $p_1 = \tfrac{1}{3}\cdot\tfrac{15}{23} = \tfrac{5}{23}$ . Trivially, $p_{20} = 1$ in this case.

Case 2: one element of $\{20,25\}$ lies in both $A$ and $B$ , while the other element lies in exactly one of $A$ and $B$ . In this case, exactly one of $20$ and $25$ lies in both $A$ and $B$ , and exactly one of $A$ and $B$ contains both $20$ and $25$ . This means that there are $2\cdot 2 = 4$ ways to assign $20$ and $25$ to $A$ and $B$ . Note that $20, 25 \in A\cup B$ . Since we must have $|A\cup B| = 17$ , there are $\tbinom{23}{15}$ ways to choose the remaining $15$ elements of $A\cup B$ , and as in the previous case, there are $3$ ways to assign each of these elements to $A$ and $B$ . Hence, $4\cdot 3^{15}\cdot\tbinom{23}{15}$ ordered pairs $(A,B)$ fall under this case.

The computation of $p_1$ in this case is identical to that in the previous case, so $p_1 = \tfrac{5}{23}$ in this case well. Recall that exactly one element of $\{20,25\}$ lies in both $A$ and $B$ . The probability that this element is $20$ is $\tfrac{1}{2}$ , so $p_{20} = \tfrac{1}{2}$ in this case.

Case 3: one element of $\{20,25\}$ lies in both $A$ and $B$ , while the other element lies in neither $A$ nor $B$ . Either $20$ or $25$ is the element that lies in both $A$ and $B$ , so there are $2$ ways to assign $20$ and $25$ to $A$ and $B$ . The case conditions imply that exactly one of $20$ and $25$ lies in $A \cup B$ , so $A\cup B$ must contain $16$ other elements. We can choose these in $\tbinom{23}{16}$ ways, and as in the two previous cases, there are $3$ ways to assign each of these elements to $A$ and $B$ . Thus, the number of ordered pairs $(A,B)$ that fall under this case is $2\cdot 3^{16}\cdot \tbinom{23}{16}$ .

The computation of $p_1$ in this case is nearly identical to that in the previous two cases, with the difference being the probability that $1\in A\cup B$ is $\tfrac{16}{23}$ (analogous reasoning still applies). Therefore, $p_1 = \tfrac{16}{23}\cdot \tfrac{1}{3} = \tfrac{16}{69}$ in this case. By the case conditions, exactly one of the elements of $\{20,25\}$ lies in both $A$ and $B$ . The probability that this element is $20$ is $\tfrac{1}{2}$ , so $p_{20} = \tfrac{1}{2}$ in this case as well.

Our casework completed, we now compute the probability that a randomly chosen ordered pair $(A,B)$ falls under each of the three cases just outlined. For simplicity, let $P_i$ denote the probability that $(A,B)$ falls under case $n$ for $n = 1,2,3$ . Then, computation gives us \begin{align*} P_1 &= \frac{3^{15}\cdot\tbinom{23}{15}}{3^{15}\cdot\tbinom{23}{15} + 4\cdot 3^{15}\cdot\tbinom{23}{15} + 2\cdot 3^{16}\cdot\tbinom{23}{16}} = \frac{1}{8} \\ P_2 &= \frac{4\cdot 3^{15}\cdot\tbinom{23}{15}}{3^{15}\cdot\tbinom{23}{15} + 4\cdot 3^{15}\cdot\tbinom{23}{15} + 2\cdot 3^{16}\cdot\tbinom{23}{16}} = \frac{1}{2} \\ P_3 &= \frac{2\cdot 3^{16}\cdot\tbinom{23}{16}}{3^{15}\cdot\tbinom{23}{15} + 4\cdot 3^{15}\cdot\tbinom{23}{15} + 2\cdot 3^{16}\cdot\tbinom{23}{16}} = \frac{3}{8}. \end{align*} Using the values that we computed for $p_1$ and $p_{20}$ in each case individually, we have \begin{align*} p_1 &= \frac{5}{23} \cdot P_1 + \frac{5}{23} \cdot P_2 + \frac{16}{69} \cdot P_3 = \frac{41}{184}\\ p_{20} &= 1 \cdot P_1 + \frac{1}{2} \cdot P_2 + \frac{1}{2} \cdot P_3 = \frac{9}{16}. \end{align*} Thus, $\mathbb{E}[|A\cap B|] = 23(\tfrac{41}{184})+ 2(\tfrac{9}{16}) = \tfrac{25}{4}$ , and we extract $25+4 = \boxed{29}$ .

~Sedro

@@ Line 4: / Line 4: @@
 ==Solution==
+For each <math>i\in \{1,2,\dots, 25\}</math>, let <math>p_i</math> denote the probability that <math>i \in A\cap B</math>, where <math>(A,B)</math> is a randomly chosen element of <math>S</math>. By the linearity of expected value,
+\begin{align*}
+\mathbb{E}[|A\cap B|] &= \mathbb{E}[p_1] + \mathbb{E}[p_2] + \cdots + \mathbb{E}[p_{25}] \\
+&= p_1 + p_2 + \cdots + p_{25}.
+\end{align*}
+(Because the value of each <math>p_i</math> is fixed, we have substituted <math>\mathbb{E}[p_i] = p_i</math>.) By symmetry, <math>p_i = p_1</math> for all valid <math>i</math> not equal to <math>20</math> or <math>25</math>, and by symmetry again, <math>p_{25} = p_{20}</math>. Therefore, <math>\mathbb{E}[|A\cap B|] = 23\cdot p_1 + 2\cdot p_{20}</math>.
+Our goal now is to find the values of <math>p_1</math> and <math>p_{20}</math>. We do this via casework on the three ways the condition <math>|(A\cap B)\cap \{20,25\}|\ge 1</math> can be met. We will compute the values of <math>p_1</math> and <math>p_{20}</math> in each case, as well as finding the number of ordered pairs <math>(A,B)</math> that fall under each case. The latter information will allow us to compute the probability that any given <math>(A,B)</math> falls under each of the three cases, which in turn will let us compute <math>p_1</math> and <math>p_{20}</math>.
+<i>Case 1:</i> both elements of <math>\{20,25\}</math> lie in both <math>A</math> and <math>B</math>. Because <math>20, 25 \in A,B</math>, we have <math>20, 25 \in A\cup B</math>. We know that <math>|A\cup B| = 17</math>, so we can choose the other <math>15</math> elements of <math>|A\cup B|</math> in <math>\tbinom{23}{15}</math> ways. There are <math>3</math> ways to assign each of these <math>15</math> elements to <math>A</math> and <math>B</math>; the element must lie in at least one of <math>A</math> and <math>B</math>, so it can lie in <math>A</math> but not in <math>B</math>, in <math>B</math> but not in <math>A</math>, or in both <math>A</math> and <math>B</math>. Therefore, there are <math>3^{15}\cdot\tbinom{23}{15}</math> ordered pairs <math>(A,B)</math> in this case.
+To find <math>p_1</math> in this case, observe that since each of the <math>23</math> elements of <math>\{1,2,\dots, 25\}</math> that are not <math>20</math> or <math>25</math> has an equal probability of being selected as an element of <math>A\cup B</math>, the probability that <math>1 \in A\cup B</math> is <math>\tfrac{15}{23}</math>. If <math>1\in A\cup B</math>, there is a <math>\tfrac{1}{3}</math> probability that <math>1 \in A\cap B</math>, so <math>p_1 = \tfrac{1}{3}\cdot\tfrac{15}{23} = \tfrac{5}{23}</math>. Trivially, <math>p_{20} = 1</math> in this case.
+<i>Case 2:</i> one element of <math>\{20,25\}</math> lies in both <math>A</math> and <math>B</math>, while the other element lies in exactly one of <math>A</math> and <math>B</math>. In this case, exactly one of <math>20</math> and <math>25</math> lies in both <math>A</math> and <math>B</math>, and exactly one of <math>A</math> and <math>B</math> contains both <math>20</math> and <math>25</math>. This means that there are <math>2\cdot 2 = 4</math> ways to assign <math>20</math> and <math>25</math> to <math>A</math> and <math>B</math>. Note that <math>20, 25 \in A\cup B</math>. Since we must have <math>|A\cup B| = 17</math>, there are <math>\tbinom{23}{15}</math> ways to choose the remaining <math>15</math> elements of <math>A\cup B</math>, and as in the previous case, there are <math>3</math> ways to assign each of these elements to <math>A</math> and <math>B</math>. Hence, <math>4\cdot 3^{15}\cdot\tbinom{23}{15}</math> ordered pairs <math>(A,B)</math> fall under this case.
+The computation of <math>p_1</math> in this case is identical to that in the previous case, so <math>p_1 = \tfrac{5}{23}</math> in this case well. Recall that exactly one element of <math>\{20,25\}</math> lies in both <math>A</math> and <math>B</math>. The probability that this element is <math>20</math> is <math>\tfrac{1}{2}</math>, so <math>p_{20} = \tfrac{1}{2}</math> in this case.
+<i>Case 3:</i> one element of <math>\{20,25\}</math> lies in both <math>A</math> and <math>B</math>, while the other element lies in neither <math>A</math> nor <math>B</math>. Either <math>20</math> or <math>25</math> is the element that lies in both <math>A</math> and <math>B</math>, so there are <math>2</math> ways to assign <math>20</math> and <math>25</math> to <math>A</math> and <math>B</math>. The case conditions imply that exactly one of <math>20</math> and <math>25</math> lies in <math>A \cup B</math>, so <math>A\cup B</math> must contain <math>16</math> other elements. We can choose these in <math>\tbinom{23}{16}</math> ways, and as in the two previous cases, there are <math>3</math> ways to assign each of these elements to <math>A</math> and <math>B</math>. Thus, the number of ordered pairs <math>(A,B)</math> that fall under this case is <math>2\cdot 3^{16}\cdot \tbinom{23}{16}</math>.
+The computation of <math>p_1</math> in this case is nearly identical to that in the previous two cases, with the difference being the probability that <math>1\in A\cup B</math> is <math>\tfrac{16}{23}</math> (analogous reasoning still applies). Therefore, <math>p_1 = \tfrac{16}{23}\cdot \tfrac{1}{3} = \tfrac{16}{69}</math> in this case. By the case conditions, exactly one of the elements of <math>\{20,25\}</math> lies in both <math>A</math> and <math>B</math>. The probability that this element is <math>20</math> is <math>\tfrac{1}{2}</math>, so <math>p_{20} = \tfrac{1}{2}</math> in this case as well.
+Our casework completed, we now compute the probability that a randomly chosen ordered pair <math>(A,B)</math> falls under each of the three cases just outlined. For simplicity, let <math>P_i</math> denote the probability that <math>(A,B)</math> falls under case <math>n</math> for <math>n = 1,2,3</math>. Then, computation gives us
+\begin{align*}
+P_1 &= \frac{3^{15}\cdot\tbinom{23}{15}}{3^{15}\cdot\tbinom{23}{15} + 4\cdot 3^{15}\cdot\tbinom{23}{15} + 2\cdot 3^{16}\cdot\tbinom{23}{16}} = \frac{1}{8} \\
+P_2 &= \frac{4\cdot 3^{15}\cdot\tbinom{23}{15}}{3^{15}\cdot\tbinom{23}{15} + 4\cdot 3^{15}\cdot\tbinom{23}{15} + 2\cdot 3^{16}\cdot\tbinom{23}{16}} = \frac{1}{2} \\
+P_3 &= \frac{2\cdot 3^{16}\cdot\tbinom{23}{16}}{3^{15}\cdot\tbinom{23}{15} + 4\cdot 3^{15}\cdot\tbinom{23}{15} + 2\cdot 3^{16}\cdot\tbinom{23}{16}} = \frac{3}{8}.
+\end{align*}
+Using the values that we computed for <math>p_1</math> and <math>p_{20}</math> in each case individually, we have
+\begin{align*}
+p_1 &= \frac{5}{23} \cdot P_1 + \frac{5}{23} \cdot P_2 + \frac{16}{69} \cdot P_3 = \frac{41}{184}\\
+p_{20} &= 1 \cdot P_1 + \frac{1}{2} \cdot P_2 + \frac{1}{2} \cdot P_3 = \frac{9}{16}.
+\end{align*}
+Thus, <math>\mathbb{E}[|A\cap B|] = 23(\tfrac{41}{184})+ 2(\tfrac{9}{16}) = \tfrac{25}{4}</math>, and we extract <math>25+4 = \boxed{29}</math>.
+~Sedro

Page

Toolbox

Search

Difference between revisions of "2025 SSMO Speed Round Problems/Problem 8"

Latest revision as of 17:14, 12 September 2025

Problem

Solution