29th BMO 1993 Problem 4 For 0 < m < 10, let S(m, n) is the set of all positive integers with n 1s, n 2s, n 3s, ... , n ms. For a positive integer N let d(N) be the sum of the absolute differences between all pairs of adjacent digits. For example, d(122313) = 1 + 0 + 1 + 2 + 2 = 6. Find the mean value of d(N) for N in S(m, n). Solution
: n(m 2 - 1)/3. Consider the number of ways of placing two different digits h and k next to each other in positions 1 and 2. The other mn - 2 digits can be permuted in (mn-2)! ways. But there are m-2 groups of n identical digits and 2 groups of n-1 identical digits, so the total number of ways is (mn-2)! / (n! m-2 (n-1)! 2 ). This is independent of the identity of h and k. There are 2(m-1) pairs h, k with difference 1, 2(m-2) pairs with difference 2, and so on, up to 2 pairs with difference m-1. Thus the total absolute difference between the first two digits (totalled over all members of S(m, n) ) is 2( (m-1)1 + (m-2)2 + ... + 1(m-1) )(mn-2)! /( n! m- 2 (n-1)! 2 ) = f(m, n). Exactly the same argument applies to the total absolute difference for positions 2 and 3, 3 and 4 and so on up to mn-1 and mn. Thus the total of d(N) over all members of S(m, n) is f(m, n) (mn-1). There are (mn)! / n! m members of S(m, n), so the mean is f(m, n) (mn-1) n! m / (mn)! . We have (m-1)1 + (m-2)2 + ... + 1(m-1) = (m + 2m + 3m + ... + m.m) - (1 2 + 2 2 + ... + m 2 ) = m 2 (m+1)/2 - m(m+1)(2m+1)/6 = m(m+1)(3m - 2m - 1)/6 = m(m 2 - 1)/6. Hence the mean is 1/3 m(m 2 - 1) n! 2 /( (n-1)! 2 mn) = n(m 2 - 1)/3. It is worth checking this for a few small values. Obviously the mean for S(1, n) = {11...1} is zero, which checks. We have S(2, 1) = {12, 21}, mean 1, which checks. We have S(2, 2) = {1122, 1212, 1221, 2112, 2121, 2211} mean 2, which checks. As a further check, we found 2(m-1 + m-2 + ... + 1) (mn-2)! / (n! m-2 (n-1)! 2 ) = m(m-1) (mn-2)! /( n! m-2 (n- 1)! 2 ) numbers with different digits in positions 1 and 2. There are also m.(mn-2)!/( n! m-1 (n-2)! ) numbers with the same first digit in positions 1 and 2. So in total we have (mn-2)!/n! m (m(m-1) n 2 + m n(n-1) ) = (mn-2)!/n! m mn ((m-1) n + n-1 ) = (mn)!/n! m as required. 29th BMO 1993 © John Scholes jscholes@kalva.demon.co.uk 14 Aug 2002