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 "2022 AIME I Problems/Problem 12"

m
m
Line 1: Line 1:
−
= Problem =
+
== Problem ==
 
For any finite set <math>X</math>, let <math>| X |</math> denote the number of elements in <math>X</math>. Define
 
For any finite set <math>X</math>, let <math>| X |</math> denote the number of elements in <math>X</math>. Define
 
<cmath>
 
<cmath>

Revision as of 23:00, 17 February 2022

Problem

For any finite set $X$, let $| X |$ denote the number of elements in $X$. Define \[ S_n = \sum | A \cap B | , \] where the sum is taken over all ordered pairs $(A, B)$ such that $A$ and $B$ are subsets of $\left\{ 1 , 2 , 3, \cdots , n \right\}$ with $|A| = |B|$. For example, $S_2 = 4$ because the sum is taken over the pairs of subsets \[ (A, B) \in \left\{ (\emptyset, \emptyset) , ( \{1\} , \{1\} ), ( \{1\} , \{2\} ) , ( \{2\} , \{1\} ) , ( \{2\} , \{2\} ) , ( \{1 , 2\} , \{1 , 2\} ) \right\} , \] giving $S_2 = 0 + 1 + 0 + 0 + 1 + 2 = 4$. Let $\frac{S_{2022}}{S_{2021}} = \frac{p}{q}$, where $p$ and $q$ are relatively prime positive integers. Find the remainder when $p + q$ is divided by 1000.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_AIME_I_Problems/Problem_12&oldid=171285"