2025 SSMO Speed Round Problems/Problem 8

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

Page

Toolbox

Search

2025 SSMO Speed Round Problems/Problem 8

Problem

Solution