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 2n​n! pairs is
(2n​)1​k=1∑n−1​k(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−1​k(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−1​k(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⋅101​k=1∑10​9k2−11k+55​=355​
and so p+q=58​.
The problems on this page are the property of the MAA's American Mathematics Competitions