HMMT 二月 2015 · 团队赛 · 第 8 题

英文解析

8. [ 40 ] Let π be a permutation of { 1 , 2 , . . . , 2015 } . With proof, determine the maximum possible numberof ordered pairs ( i, j ) ∈ { 1 , 2 , . . . , 2015 } with i < j such that π ( i ) · π ( j ) > i · j .2
   ( )
   2014
   Answer: Let n = 2015. The only information we will need about n is that n > 5. For the 4
   construction, take π to be the n -cycle defined by 2
   {
   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 .
   π ( i )2
   For convenience let z = , so that we are trying to maximize the number of pairs ( i, j ) , i < jiwith z z > 1. Notice that over any cycle c = ( i i · · · i ) in the cycle decomposition of π we haveii j 1 2 k
   ∏ ∏
   z = 1. In particular, multiplying over all such cycles gives z = 1.ni ii ∈ c i =1
   Construct a graph G on vertex set V = [ n ] such that there is an edge between i and j whenever
   ∏ ∏
   2 kπ ( i ) π ( j ) > ij . For any cycle C = ( v , v , . . . , v ) in this graph we get 1 < z z = z .
   1 2 k v vi i +1 vi =1 v ∈ C
   So, we get in particular that G is non-Hamiltonian.
   By the contrapositive of Ore’s theorem, there are two distinct indices u, v ∈ [ n ] such that d ( u )+ d ( v ) ≤5
   ( ) ( )
   n − 2 n − 1
   n − 1. The number of edges is then at most + ( n − 1) = + 1.
   2 2
   which generally underlies a great deal of complex analysis 3
   ( )
   If you want, you can try running a computer check for n ≤ 5. One of the problem czars believes the answer is still = 644
   (compare with the Remark at the end for a looser general problem) based on computer program, but didn’t check carefully.2
   see also this Stack exchange thread 5
   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 atleast 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 acomplete graph, we can pick a Hamiltonian path in G \ { u, v, w } with endpoints a, b . Connecting u tothe ends of this path forms an ( n − 2)-cycle C .
   ∏ ∏
   2 n
   This gives us z > 1. But we also have z z > 1, so 1 = z > 1, contradiction.
   v w ixx ∈ 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 thei i
   ( )2
   n − 1
   best possible. If n = 5, then we can get 1 + = 7: consider exponentiating the zero-sum set
   2 2 22
   { t, t, t − t, t − t, − 2 t } for some sufficiently small t . A computer check would easily determine whethera construction exists in the original permutation setting. (If the following code is correct, the answeris ‘no’, i.e. 6 is the best: see http://codepad.org/Efsv 8Suy .)
   2 πi 2 πi
   101 10