CombinatoricsDifficulty 5.4AIME, harderFind the answer
Let π be a permutation of {1,2,…,2015}. With proof, determine the maximum possible number of ordered pairs (i,j)∈{1,2,…,2015}2 with i<j such that π(i)⋅π(j)>i⋅j.
A number or a short expression. Spacing and $ signs are ignored.
Solution
Let n=2015. The only information we will need about n is that n>544. For the construction, take π to be the n-cycle defined by π(k)={k+11 if 1≤k≤n−1 if k=n. Then π(i)>i for 1≤i≤n−1. So π(i)π(j)>ij for at least (2n−1) pairs i<j. For convenience let zi=iπ(i), so that we are trying to maximize the number of pairs (i,j),i<j with zizj>1. Notice that over any cycle c=(i1i2⋯ik) in the cycle decomposition of π we have ∏i∈czi=1. In particular, multiplying over all such cycles gives ∏i=1nzi=1. Construct a graph G on vertex set V=[n] such that there is an edge between i and j whenever π(i)π(j)>ij. For any cycle C=(v1,v2,…,vk) in this graph we get 1<∏i=1kzvizvi+1=∏v∈Czv2. 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)≤n−1. The number of edges is then at most (2n−2)+(n−1)=(2n−1)+1. 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=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. This gives us ∏x∈Czx2>1. But we also have zvzw>1, so 1=∏i=inzi>1, contradiction. So, (2n−1)+1 cannot be attained, and (2n−1) is indeed the maximum number of pairs possible.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: Omni-MATH,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.