Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2023 SSMO Team Round Problems/Problem 7"

(Created page with "==Problem== Let <math>S = \{1, 2, 3, 4, \cdots, 23\}</math> and let there be randomly chosen sets <math>A, B, C</math> where <math>A, B, C \subseteq S</math>. The probability...")
 
 
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
 +
The number of ordered triples <math>(A, B, C)</math> that satisfy the given property is equal to 
 +
<cmath>\sum_{1 \le a, b,\, a + b \le 23} \binom{23}{a} \binom{23}{b} \binom{23}{a + b}.</cmath>
 +
 +
Substituting <math>c = 23 - a - b</math>, this becomes 
 +
<cmath>\sum_{a + b + c = 23} \binom{23}{a} \binom{23}{b} \binom{23}{c}.</cmath>
 +
 +
We now evaluate this sum in two ways.
 +
 +
===Method 1===
 +
Consider a set <math>A</math> of 69 elements, partitioned into three disjoint subsets <math>A_1</math>, <math>A_2</math>, and <math>A_3</math>, each of size 23. Choosing any 23 elements from <math>A</math> corresponds to choosing <math>a</math> from <math>A_1</math>, <math>b</math> from <math>A_2</math>, and <math>c</math> from <math>A_3</math> such that <math>a + b + c = 23</math>. This is a bijection to the sum, so the value is 
 +
<cmath>\binom{69}{23}.</cmath>
 +
 +
===Method 2===
 +
By the binomial theorem, <cmath>(x + 1)^{23} = \sum_{i = 0}^{23} \binom{23}{i} x^i,</cmath> so the sum is the coefficient of <math>x^{23}</math> in <math>((x + 1)^{23})^3 = (x + 1)^{69}</math>, which is again 
 +
<cmath>\binom{69}{23}.</cmath>
 +
 +
The total number of possible ordered subsets <math>(A, B, C)</math> is <math>2^{23} \cdot 2^{23} \cdot 2^{23} = 2^{69}</math>, so the desired probability is 
 +
<cmath>\frac{\binom{69}{23}}{2^{69}}.</cmath>
 +
 +
To find the greatest power of 2 dividing this expression, note that 
 +
<cmath>\binom{69}{23} = \frac{69!}{23! \cdot 46!}.</cmath>
 +
 +
Using Legendre’s formula for <math>\nu_2(n!)</math>, 
 +
<cmath>\nu_2(\binom{69}{23}) = \nu_2(69!) - \nu_2(46!) - \nu_2(23!) = 65 - 44 - 16 = 5.</cmath>
 +
 +
So the power of 2 in the denominator is 69, and in the numerator is 5, leaving a net power of 
 +
<cmath>69 - 5 = \boxed{64}.</cmath>
 +
 +
~SMO_Team

Latest revision as of 21:23, 9 September 2025

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}}.\]

To find the greatest power of 2 dividing this expression, note that \[\binom{69}{23} = \frac{69!}{23! \cdot 46!}.\]

Using Legendre’s formula for $\nu_2(n!)$, \[\nu_2(\binom{69}{23}) = \nu_2(69!) - \nu_2(46!) - \nu_2(23!) = 65 - 44 - 16 = 5.\]

So the power of 2 in the denominator is 69, and in the numerator is 5, leaving a net power of \[69 - 5 = \boxed{64}.\]

~SMO_Team

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_SSMO_Team_Round_Problems/Problem_7&oldid=260186"