Problem:
Let S={20,21,22,…,210}. Consider all possible positive differences of pairs of elements of S. Let N be the sum of all of these differences. Find the remainder when N is divided by 1000.
Solution:
For n≥1, let Tn denote the sum of all positive differences of all pairs of elements of the set {20,21,22,…,2n}. Given two elements in this set, if neither equals 2n, then the difference of these elements contributes to the sumTn−1. Thus
Tn=Tn−1+(2n−2n−1)+(2n−2n−2)+⋯+(2n−20)=Tn−1+n⋅2n−(2n−1)
By applying this recursion repeatedly, it follows that
Tn=k=1∑n(k⋅2k−2k+1)=k=1∑nk⋅2k−k=1∑n2k+k=1∑n1=(k=1∑nk⋅2k)−(2n+1−2)+n=(k=1∑n(i=k∑n2i))−(2n+1−2)+n=(k=1∑n2−12k(2n−k+1−1))−(2n+1−2)+n=(k=1∑n(2n+1−2k))−(2n+1−2)+n=n⋅2n+1−(2n+1−2)−(2n+1−2)+n=(n−2)2n+1+n+4
Setting n=10 gives T10=214+14=16398. Thus the required remainder is 398.
The problems on this page are the property of the MAA's American Mathematics Competitions