Maths Olympiad Prep

Library / /695 of 860

Combinatorics Difficulty 5.4 AIME, harder Find the answer

Let π\pi be a permutation of {1,2,,2015}\{1,2, \ldots, 2015\}. With proof, determine the maximum possible number of ordered pairs (i,j){1,2,,2015}2(i, j) \in\{1,2, \ldots, 2015\}^{2} with i<ji<j such that π(i)π(j)>ij\pi(i) \cdot \pi(j)>i \cdot j.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let n=2015n=2015. The only information we will need about nn is that n>544n>5 \sqrt[4]{4}. For the construction, take π\pi to be the nn-cycle defined by π(k)={k+1 if 1kn11 if k=n\pi(k)= \begin{cases}k+1 & \text { if } 1 \leq k \leq n-1 \\ 1 & \text { if } k=n\end{cases}. Then π(i)>i\pi(i)>i for 1in11 \leq i \leq n-1. So π(i)π(j)>ij\pi(i) \pi(j)>i j for at least (n12)\binom{n-1}{2} pairs i<ji<j. For convenience let zi=π(i)iz_{i}=\frac{\pi(i)}{i}, so that we are trying to maximize the number of pairs (i,j),i<j(i, j), i<j with zizj>1z_{i} z_{j}>1. Notice that over any cycle c=(i1i2ik)c=\left(i_{1} i_{2} \cdots i_{k}\right) in the cycle decomposition of π\pi we have iczi=1\prod_{i \in c} z_{i}=1. In particular, multiplying over all such cycles gives i=1nzi=1\prod_{i=1}^{n} z_{i}=1. Construct a graph GG on vertex set V=[n]V=[n] such that there is an edge between ii and jj whenever π(i)π(j)>ij\pi(i) \pi(j)>i j. For any cycle C=(v1,v2,,vk)C=\left(v_{1}, v_{2}, \ldots, v_{k}\right) in this graph we get 1<i=1kzvizvi+1=vCzv21<\prod_{i=1}^{k} z_{v_{i}} z_{v_{i+1}}=\prod_{v \in C} z_{v}^{2}. So, we get in particular that GG is non-Hamiltonian. By the contrapositive of Ore's theorem there are two distinct indices u,v[n]u, v \in[n] such that d(u)+d(v)n1d(u)+d(v) \leq n-1. The number of edges is then at most (n22)+(n1)=(n12)+1\binom{n-2}{2}+(n-1)=\binom{n-1}{2}+1. If equality is to hold, we need G\{u,v}G \backslash\{u, v\} to be a complete graph. We also need d(u)+d(v)=n1d(u)+d(v)=n-1, with uvu v not an edge. This implies d(u),d(v)1d(u), d(v) \geq 1. Since n>5n>5, the pigeonhole principle gives that at least one of u,vu, v has degree at least 3. WLOG d(u)3d(u) \geq 3. Let ww be a neighbor of vv and let a,b,ca, b, c be neighbors of uu; WLOG wa,bw \neq a, b. Since G\{u,v,w}G \backslash\{u, v, w\} is a complete graph, we can pick a Hamiltonian path in G\{u,v,w}G \backslash\{u, v, w\} with endpoints a,ba, b. Connecting uu to the ends of this path forms an (n2)(n-2)-cycle CC. This gives us xCzx2>1\prod_{x \in C} z_{x}^{2}>1. But we also have zvzw>1z_{v} z_{w}>1, so 1=i=inzi>11=\prod_{i=i}^{n} z_{i}>1, contradiction. So, (n12)+1\binom{n-1}{2}+1 cannot be attained, and (n12)\binom{n-1}{2} 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.