Problem:
For each permutation a1,a2,a3,…,a10 of the integers 1,2,3,…,10, form the sum
∣a1−a2∣+∣a3−a4∣+∣a5−a6∣+∣a7−a8∣+∣a9−a10∣
The average value of all such sums can be written in the form p/q, where p and q are relatively prime positive integers. Find p+q.
Solution:
Consider the average of all sums of the form
∣a1−a2∣+∣a3−a4∣+⋯+∣an−1−an∣
where n is even and (a1,a2,a3,…,an) is a permutation of (1,2,3,…,n). Each of the n ! sums contains n/2 differences of pairs of integers. There are (2n) such pairs. For each k=1,2,…,n−1, there are n−k of these (2n) pairs with difference k. Because each of these pairs occurs the same number of times in the n! sums, the average of the differences of all 2nn! pairs is
(2n)1k=1∑n−1k(n−k)
Because k(n−k) is the number of subsets {a,k+1,b} of {1,2,…,n+1} that have a<k+1<b, it follows that
k=1∑n−1k(n−k)=(3n+1)
The average difference is therefore (2n)(3n+1)=3n+1. The average sum of n/2 differences is 6n(n+1), which equals 55/3 when n=10. Thus p+q=58.
Note: When n=10, it is easy to calculate the value of ∑k=1n−1k(n−k) directly.
OR
The average is just 5 times the average value of ∣a1−a2∣, because the average value of ∣a2i−1−a2i∣ is the same for i=1,2,3,4,5. When a1=k, the average value of ∣a1−a2∣ is
9(k−1)+(k−2)+⋯+1+1+2+⋯+(10−k)=91[2k(k−1)+2(10−k)(11−k)]=9k2−11k+55
Thus the average value of the sum is
5⋅101k=1∑109k2−11k+55=355
and so p+q=58.
The problems on this page are the property of the MAA's American Mathematics Competitions