Problem:
For any finite set X, let ∣X∣ denote the number of elements in X. Define
Sn=∑∣A∩B∣
where the sum is taken over all ordered pairs (A,B) such that A and B are subsets of {1,2,3,⋯,n} with ∣A∣=∣B∣. For example, S2=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})}
giving S2=0+1+0+0+1+2=4. Let S2021S2022=qp, where p and q are relatively prime positive integers. Find the remainder when p+q is divided by 1000.
Solution:
Suppose we choose a subset of size k, and we are choosing from {1,2,3,...,n}.
then, the probability any of the numbers 1,2,...,n is in the first set is nk, and the probability that it would be in the second is nk, so by linearity of expectation the expected number would be
n⋅nk⋅nk
and we'd sum this times the number of ways to choose the subsets over all possible subset sizes to get the sum
k=1∑nn⋅nknk⋅(kn)2
From here, we can simplify this summation by expanding the binomial to get
nk=1∑n(k−1n−1)(n−kn−1)
We can simplify this using Vandermonde's identity, which is as follows:
(rm+n)=k=0∑r(km)(r−kn)
In this case, we'd have that
nk=1∑n(k−1n−1)(n−kn−1)=n(n−12n−2)
Plugging in appropriate values for 2022 and 2021 yields an answer of
2021(20204040)2022(20214042)=202132022⋅4042⋅4041
and the sum of numerator and denominator mod 1000 is \boxed
The problems on this page are the property of the MAA's American Mathematics Competitions