Un Peu de Math
The following was triggered by a math
At first sight this seemed quite diffficult, and Granville launched a math [Note to my readers: this post is unusually technical. However,, it only uses high school mathematics, and it is self contained.] The ProblemLet me state the definition of q here. Let x be a permutation of the integers from 0 to n-1: x is a function such that x(i) is in the set {0,1,...,n-1} for all i in that set. Furthermore, x(i) is different from x(j) whenever i is different from j. In what follows all permutations are permutations of 0..n-1. We define three functions of x, where |a| stands for the absolute value of a: u(x) = sum_{i} |x(i) - i| v(x) = sum_{i} |(x(i) - (n-1- i)| t(x) = min( u(x), v(x) ). Let q(n) be the maximum of t(x) over all permutations x. The problem is to compute q(n) for all n We will first give our answer, then provide the proof that the answer is correct.
The AnswerLet m be the quotient and let r be the remainder of the Euclidean division of n by 4: n = 4m + r, 0 <= r < 4. Let (1) p(n) = 6m^{2} + 3mr + r(r-1)/2 We prove the following two equalities in this post: (2) q(n) = p(n) if p(n) is even (3) q(n) = p(n) - 1 if p(n) is odd Let's make some observations before providing the proof. First, p(n) is even if r=0, or if r=1 and m is even, or if r=3 and m is odd; p(n) is odd if r=2, or if r=1 and m is odd, or if r=3 and m is even. Second, using m= (n-r)/4 we get p(n) = 3m(2m+r)+ r(r-1)/2 = 3[(n-r)/4][(n-r)/2 + r] + r(r-1)/2 = 3/8 (n-r)(n + r)+ r(r-1) = 3/8 (n^{2} - r^{2}) + r(r-1)/2 Hence p(n) = 3/8 n^{2}-1/8 r^{2} + 1/2 r Therefore, p(n) and q(n) are asymptotically equal to 3n^{2}/8 Third, we can explicitly compute q(n) in term of n. The values are provided in Table 1. ( n modulo 8 is the remainder of n in the Euclidean division of n by 8.)
Table 1. Value of p(n) and q(n) for all n Let us show how to compute the case n modulo 8 = 5, the other cases being similar. In this case n = 8a+5 for some a, m = 2a+1, and r = 1. We have r=1 and m odd, hence p(n) is odd, and q(n) = p(n) - 1 = 3/8 (n^{2} - r^{2}) +r(r-1)/2 - 1 = 3/8 (n^{2}- 1) - 1
An Upper BoundLet's now provide the proof of equalities (2) and (3). We first prove that q(n) <= p(n) Let x be a permutation, and let w(x) = u(x) + v(x). By definition of t, 2 t(x) <= u(x) + v(x) = w(x) We have w(x) = sum_i f(i,x(i)) , where f(i,j) = |j - i| + |j - (n-1-i)| Let's compute the value f(i,j) for each cell (i,j) of the n by n square. It is easy to check that the cells having the same value are arranged in concentric rings as depicted in Fig. 1. The ring R_{k} is the set of cells (i,j) such that one of the following conditions is true (i) k <= i <= n-1-k & j = k (ii) k <= i <= n-1-k & j = n-1-k (ii) k <= j <= n-1-k & i = k (iv) k <= j <= n-1-k & i = n-1-k The value of f for the cells in R_{k} is n-1-2k Figure 1. Value of f over the nxn square. The blue region is the ring R_{k}. The value of the cells in R_{k} is n-1-2k A permutation x defines a set of n cells in the square such that there is exactly one cell per row, and exactly one cell per column. This set is { (i,x(i)) | 0 <= i < n}. Note that there are at most 4 such cells in a given ring (at most one for each side of the ring). Finding the maximum of w(x) over all permutations amounts to selecting such set that maximizes the sum of the value of its cells. Since the value of cells in rings decreases with k, the maximum is obtained by selecting as many cells as possible from the rings in increasing values of k. It means selecting 4 cells in each of the first m rings then r cells in the m-th ring. Therefore w(x) <= r(n-1-2m) + 4 sum_{0<=k<m}(n-1-2k) Elementary calculus yields r(n-1-2m) + 4 sum_{0<=k<m}(n-1-2k) = r(4m + r - 1 - 2m) + 4m(n-1) - 8 sum_{0<=k<m}k = r(2m + r - 1) + 4m(4m + r -1) - 4m(m-1) = 12 m^{2} + 6 mr + r(r-1) Therefore, we have w(x) <= 2p(n) where p(n) = 6 m^{2} + 3 mr + r(r-1)/2 Then t(x) <= w(x)/2 <= p(n) The above is valid for any permutation x, which entails (4) q(n) <= p(n)
A Better Upper BoundLet x be a permutation. We have sum_{i} x(i) = sum_{i} i Then, u(x) = sum_{i }|x(i) - i| = sum_{x(i)>i} (x(i) - i) - sum_{x(i)<i} (x(i) - i) = sum_{i} (x(i) - i) - 2 sum_{x(i) < i} (x(i) - i) = - 2 sum_{x(i) < i}(x(i) - i) Then u(x) is even. Note that v(x) = u(x^{'}), where x^{'} is defined by x^{'}(i) = x(n-1-i). Therefore v(x) is even, and t(x) is even. This is true for all permutations x hence q(n) is even. Then the bound in (4) can be lowered by 1 when p(n) is odd: (5) q(n) <= p(n) - 1 if p(n) is odd The original bound is still valid in the remaining cases: (6) q(n) <= p(n) if p(n) is even
A Lower BoundWe complete our proof by constructing permutations x for which t(x) equals the right hand side of inequalities (5) and (6). We construct these permutations by selecting m cells in each of the areas A,B,C,D of the nxn square, and r cells in the ring R of the nxn square. These regions are depicted on Fig. 2. Figure 2. Areas used for constructing optimal permutations A is the set of cells (i, x(i)) with 0 <= i < m, m <= x(i) < n-m B is the set of cells (i, x(i)) with m <= i < n- m, n-m <= x(i) < n C is the set of cells (i, x(i)) with n-m <= i < n, m <= x(i) < n-m D is the set of cells (i, x(i)) with m <= i < n-m,0 <= x(i) < m R is the ring R_{m} More precisely, we select one cell for each column in A, for each column in C, for each row in B, and for each row in D. It means that we select 4 cells in each of the first m rings R_{k}. By the above computations it entails w(x) = 2p(n). If p(n) is even, then we construct x such that u(x) = p(n). In this case, v(x) = w(x) - u(x) = p(n), and t(x) = min(u(x), v(x)) = p(n). Therefore q(n) >= t(x) = p(n). Together with (6) it entails q(n) = p(n) If p(n) is odd, then we construct x such that u(x) = p(n) - 1. In this case, v(x) = w(x) - u(x) = p(n)+1, and t(x) = min(u(x), v(x)) = p(n) - 1. Therefore q(n) >= t(x) = p(n) - 1. Together with (5) it entails q(n) = p(n) - 1. Let's now describe the permutations we constructed, which concludes our proof. We distinguish 4 cases corresponding to the possible remainder r of the Euclidean division or n by 4. Note the similarity between x^{0} and x^{4} (Fig. 3 and Fig. 7), as well as the similarity between x^{1} and x^{5} (Fig. 4 and Fig. 8).
Case r = 0In this case, we have n = 4m, p(n) = 6 m^{2}, and p(n) even. Let x^{0} be the permutation (see Fig. 3):
We have u(x^{0}) = m^{2} + 2m^{2} + 2m^{2} + m^{2} = 6m^{2} = p(n) Figure 3. The permutation x^{0}. Case r = 2In this case, we have n = 4m+2, p(n) = 6 m^{2} + 6 m + 1, , and p(n) odd. Let x^{4} be the permutation (see Fig. 7):
We have u(x^{4}) = m(m+1) + (m+1)(2m) + m(2m+2) + m(m+1) = 6m^{2} + 6m = p(n) -1 Figure 7. The permutation x^{4}. Note the similarity with x^{0} Case r = 1In this case, we have n = 4m+1, and p(n) = 6 m^{2} + 3 m. Let a be the quotient and b be the remainder of the euclidean division of m by 2: m = 2a+b, 0<= b <= 1. Let x^{1} be the permutation (see Fig 4.):
We have u(x^{1}) = m(m+1) + a(2m+1) + a + (m-a)(2m) + m(2m+1) + m^{2} = 6m^{2} + 2m +2a If m is even, then p(n) is even, and 2a = m. We then have u(x^{1}) = 6m^{2} + 3m = p(n) If m is odd, then p(n) is odd, and 2a = m-1. We then have u(x^{1}) = 6m^{2} + 3m - 1 = p(n) - 1
Figure 4. The permutation x^{1}. Case r = 3In this case, we have n = 4m+3, and p(n) = 6 m^{2} + 9 m + 3. Let a be the quotient and b be the remainder of the euclidean division of m by 2: m = 2a+b, 0<= b <= 1. Let x6 be the permutation (see Fig. 6):
We have u(x^{3}) = m(m+1) + 2m+2 + (m-a-1)(2m+2) + m-a + (a+1)(2m+1) + m(2m+2) + m+1 + m(m+1) = 4m^{2} + 8m +3 + 2m(m-a-1 + a+1) + 2(m-a-1) - a + a+1 = 6m^{2} + 10m - 2a + 2 If m is even, then p(n) is odd, and 2a = m. We then have u(x^{3}) = 6m^{2} + 9m + 2 = p(n) - 1 If m is odd, then p(n) is even, and 2a = m-1. We then have u(x^{3}) = 6m^{2} + 9m + 3 = p(n)
Figure 8. The permutation x^{5}. Note the similarity with x^{1}. |