2023 SSMO Team Round Problems/Problem 7

Problem

Let $S = \{1, 2, 3, 4, \cdots, 23\}$ and let there be randomly chosen sets $A, B, C$ where $A, B, C \subseteq S$ . The probability that $|A| + |B| = |C|$ can be expressed as $\frac{m}{n}$ . Let $2^a$ be the largest power of $2$ such $2^a \mid n$ . Find $a$ .

Solution

The number of ordered triples $(A, B, C)$ that satisfy the given property is equal to $\sum_{1 \le a, b,\, a + b \le 23} \binom{23}{a} \binom{23}{b} \binom{23}{a + b}.$

Substituting $c = 23 - a - b$ , this becomes $\sum_{a + b + c = 23} \binom{23}{a} \binom{23}{b} \binom{23}{c}.$

We now evaluate this sum in two ways.

Method 1

Consider a set $A$ of 69 elements, partitioned into three disjoint subsets $A_1$ , $A_2$ , and $A_3$ , each of size 23. Choosing any 23 elements from $A$ corresponds to choosing $a$ from $A_1$ , $b$ from $A_2$ , and $c$ from $A_3$ such that $a + b + c = 23$ . This is a bijection to the sum, so the value is $\binom{69}{23}.$

Method 2

By the binomial theorem, $(x + 1)^{23} = \sum_{i = 0}^{23} \binom{23}{i} x^i,$ so the sum is the coefficient of $x^{23}$ in $((x + 1)^{23})^3 = (x + 1)^{69}$ , which is again $\binom{69}{23}.$

The total number of possible ordered subsets $(A, B, C)$ is $2^{23} \cdot 2^{23} \cdot 2^{23} = 2^{69}$ , so the desired probability is $\frac{\binom{69}{23}}{2^{69}}.$