HMMT 二月 2015 · 团队赛 · 第 8 题
HMMT February 2015 — Team Round — Problem 8
题目详情
- [ 40 ] Let π be a permutation of { 1 , 2 , . . . , 2015 } . With proof, determine the maximum possible number 2 of ordered pairs ( i, j ) ∈ { 1 , 2 , . . . , 2015 } with i < j such that π ( i ) · π ( j ) > i · j . 2 πi 2 πi 101 10
解析
- [ 40 ] Let π be a permutation of { 1 , 2 , . . . , 2015 } . With proof, determine the maximum possible number 2 of ordered pairs ( i, j ) ∈ { 1 , 2 , . . . , 2015 } with i < j such that π ( i ) · π ( j ) > i · j . ( ) 2014 4 Answer: Let n = 2015. The only information we will need about n is that n > 5. For the 2 construction, take π to be the n -cycle defined by { k + 1 if 1 ≤ k ≤ n − 1 π ( k ) = 1 if k = n. ( ) n − 1 Then π ( i ) > i for 1 ≤ i ≤ n − 1. So π ( i ) π ( j ) > ij for at least pairs i < j . 2 π ( i ) For convenience let z = , so that we are trying to maximize the number of pairs ( i, j ) , i < j i i with z z > 1. Notice that over any cycle c = ( i i · · · i ) in the cycle decomposition of π we have i j 1 2 k ∏ ∏ n z = 1. In particular, multiplying over all such cycles gives z = 1. i i i ∈ c i =1 Construct a graph G on vertex set V = [ n ] such that there is an edge between i and j whenever ∏ ∏ k 2 π ( i ) π ( j ) > ij . For any cycle C = ( v , v , . . . , v ) in this graph we get 1 < z z = z . 1 2 k v v i i +1 v i =1 v ∈ C So, we get in particular that G is non-Hamiltonian. 5 By the contrapositive of Ore’s theorem, there are two distinct indices u, v ∈ [ n ] such that d ( u )+ d ( v ) ≤ ( ) ( ) n − 2 n − 1 n − 1. The number of edges is then at most + ( n − 1) = + 1. 2 2 3 which generally underlies a great deal of complex analysis ( ) 4 4 If you want, you can try running a computer check for n ≤ 5. One of the problem czars believes the answer is still = 6 2 (compare with the Remark at the end for a looser general problem) based on computer program, but didn’t check carefully. 5 see also this StackExchange thread Team If equality is to hold, we need G \ { u, v } to be a complete graph. We also need d ( u ) + d ( v ) = n − 1, with uv not an edge. This implies d ( u ) , d ( v ) ≥ 1. Since n > 5, the pigeonhole principle gives that at least one of u, v has degree at least 3. WLOG d ( u ) ≥ 3. Let w be a neighbor of v and let a, b, c be neighbors of u ; WLOG w 6 = a, b . Since G \ { u, v, w } is a complete graph, we can pick a Hamiltonian path in G \ { u, v, w } with endpoints a, b . Connecting u to the ends of this path forms an ( n − 2)-cycle C . ∏ ∏ n 2 This gives us z > 1. But we also have z z > 1, so 1 = z > 1, contradiction. v w i x x ∈ C i = i ( ) ( ) n − 1 n − 1 So, + 1 cannot be attained, and is indeed the maximum number of pairs possible. 2 2 Remark. Let’s think about the more general problem where we forget about the permutation structure ( ) ∏ n − 1 (and only remember z = 1 and z > 0). If n = 4 it’s easy to show by hand that is still the i i 2 ( ) n − 1 best possible. If n = 5, then we can get 1 + = 7: consider exponentiating the zero-sum set 2 2 2 2 { t, t, t − t, t − t, − 2 t } for some sufficiently small t . A computer check would easily determine whether a construction exists in the original permutation setting. (If the following code is correct, the answer is ‘no’, i.e. 6 is the best: see http://codepad.org/Efsv8Suy .) 2 πi 2 πi 101 10