MathDB
It's not like I share elements with you or anything, baka!

Source: AIME I #12

February 9, 2022
AIME I 12

Problem Statement

For any finite set XX, let ∣X∣|X| denote the number of elements in X.X. Define Sn=∑∣A∩B∣,S_n = \sum |A \cap B|, where the sum is taken over all ordered pairs (A,B)(A, B) such that AA and BB are subsets of {1,2,3,…,n}\{1, 2, 3, …, n\} with ∣A∣=∣B∣.|A| = |B|. For example, S2=4S_2 = 4 because the sum is taken over the pairs of subsets (A,B)∈{(∅,∅),({1},{1}),({1},{2}),({2},{1}),({2},{2}),({1,2},{1,2})},(A, B) \in \{ (\emptyset, \emptyset), (\{1\}, \{1\}), (\{1\}, \{2\}), (\{2\}, \{1\}), (\{2\}, \{2\}), (\{1, 2\}, \{1, 2\})\}, giving S2=0+1+0+0+1+2=4.S_2 = 0 + 1 + 0 + 0 + 1 + 2 = 4. Let S2022S2021=pq,\frac{S_{2022}}{S_{2021}} = \frac{p}{q}, where pp and qq are relatively prime positive integers. Find the remainder when p+qp + q is divided by 1000.1000.
Back to ProblemsView on AoPS