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:
Answer (245):
For any element x of {1,2,3,…,n}, the number of occurrences of x in an intersection of two (not necessarily different) subsets with k elements each is (k−1n−1)2. Using the identity
k=0∑n(kn)2=k=0∑n(kn)(n−kn)=(n2n)
it follows that the number of occurrences of x in an intersection of two subsets with the same number of elements is
k=1∑n(k−1n−1)2=k=0∑n−1(kn−1)2=(n−12n−2)
Thus
Sn=n(n−12n−2)
Therefore
Sn−1Sn=(n−22n−4)(n−1)(n−12n−2)n=(2n−4)!(n−1)!2⋅(n−1)(2n−2)!(n−2)!2⋅n=(n−1)22n(2n−3)
which is always in lowest terms when n is even because 2n=2(n−1)+2 and 2n−3=2(n−1)−1. Substituting n=2022 yields
S2021S2022=202124044⋅4041
When 4044⋅4041+20212 is divided by 1000 , the remainder is the same as the remainder when 44⋅41+212=2245 is divided by 1000 . Thus the requested remainder is 245 .
Note: The sequence Sn is sequence A037965 in the On-Line Encyclopedia of Integer Sequences.
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions