, 2015

Solution:
Answer: $\dbinom{2014}{2}$

Let $n=2015$. The only information we will need about $n$ is that $n>5$.

For the construction, take $\pi$ to be the $n$-cycle defined by
$$\pi(k)= \begin{cases}k+1 & \text{ if } 1 \leq k \leq n-1 \\ 1 & \text{ if } k=n\end{cases}$$
Then $\pi(i)>i$ for $1 \leq i \leq n-1$. So $\pi(i) \pi(j)>i j$ for at least $\binom{n-1}{2}$ pairs $i<j$.

For convenience let $z_{i}=\frac{\pi(i)}{i}$, so that we are trying to maximize the number of pairs $(i, j), i<j$ with $z_{i} z_{j}>1$. Notice that over any cycle $c=\left(i_{1} i_{2} \cdots i_{k}\right)$ in the cycle decomposition of $\pi$ we have $\prod_{i \in c} z_{i}=1$. In particular, multiplying over all such cycles gives $\prod_{i=1}^{n} z_{i}=1$.

Construct a graph $G$ on vertex set $V=[n]$ such that there is an edge between $i$ and $j$ whenever $\pi(i) \pi(j)>i j$. For any cycle $C=\left(v_{1}, v_{2}, \ldots, v_{k}\right)$ in this graph we get $1<\prod_{i=1}^{k} z_{v_{i}} z_{v_{i+1}}=\prod_{v \in C} z_{v}^{2}$. So, we get in particular that $G$ is non-Hamiltonian.

By the contrapositive of Ore's theorem there are two distinct indices $u, v \in[n]$ such that $d(u)+d(v) \leq n-1$. The number of edges is then at most $\binom{n-2}{2}+(n-1)=\binom{n-1}{2}+1$.

If equality is to hold, we need $G \setminus\{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) \geq 1$. Since $n>5$, the pigeonhole principle gives that at least one of $u, v$ has degree at least $3$. WLOG $d(u) \geq 3$.

Let $w$ be a neighbor of $v$ and let $a, b, c$ be neighbors of $u$; WLOG $w \neq a, b$. Since $G \setminus\{u, v, w\}$ is a complete graph, we can pick a Hamiltonian path in $G \setminus\{u, v, w\}$ with endpoints $a, b$. Connecting $u$ to the ends of this path forms an $(n-2)$-cycle $C$.

This gives us $\prod_{x \in C} z_{x}^{2}>1$. But we also have $z_{v} z_{w}>1$, so $1=\prod_{i=1}^{n} z_{i}>1$, contradiction.

So, $\binom{n-1}{2}+1$ cannot be attained, and $\binom{n-1}{2}$ is indeed the maximum number of pairs possible.