BarcelonaTech Mathcontest

We say a pair $(a, b)$ is a-good if $a > b \ge f(a)$, and b-good if $b \le f(a) < f(b)$. If $f(k) = k$, no pair $(k, b)$ or $(a, k)$ is k-good. If $f(k) > k$, there are no k-good pairs of the form $(k, b)$ and exactly $f(k) - k$ of the form $(a, k)$. Likewise, if $f(k) < k$ there are exactly $k - f(k)$ k-good pairs. In any case, there are exactly $|f(k) - k|$ k-good pairs.
For every pair $(a, b)$ with $a > b$ and $f(a) < f(b)$, the pair is a-good if $f(a) \le b$, and b-good if $f(a) \ge b$. The number of pairs counted in $v$ is at most the number of good pairs, which is less than or equal to the sum of the $|f(k) - k|$. So, $v \le \sum_{k=1}^{n} |f(k) - k| = u$. Let $k$ be the smallest integer with $f(k) \ne k$. Then $f(k) > k$, $f^{-1}(k) > k$. The pair $(f^{-1}(k), k)$ is both $f^{-1}(k)$-good and $k$-good. Equality does not hold, and $v < u$.

Let $A_k = \{f^{-1}(1), f^{-1}(2), \dots, f^{-1}(f(k))\}$ and $B_k = \{1, 2, \dots, k\}$. The element $x$ is in $B_k$ and not in $A_k$ if and only if $(k, x)$ is a pair counted in $v$. Similarly, $x$ is in $A_k$ and not in $B_k$ if and only if $(x, k)$ is a pair counted in $v$. Then, $2v = \sum_{k=1}^{n} |A_k \setminus B_k| + |B_k \setminus A_k| = \sum_{k=1}^{n} |A_k| + |B_k| - 2|A_k \cap B_k| \ge \sum_{k=1}^{n} |A_k| + |B_k| - 2 \min\{|A_k|, |B_k|\} = \sum_{k=1}^{n} f(k) + k - 2 \min\{f(k), k\} = \sum_{k=1}^{n} |f(k) - k| = u$.

We look at the equality case. $u = 2v \iff |A_b \cap B_b| = \min\{|A_b|, |B_b|\}$ for all $b \iff A_b \subseteq B_b$ or $B_b \subseteq A_b$ for all $b \iff$ There do not exist $a, b, c$ such that $a \in A_b \setminus B_b$, $c \in B_b \setminus A_b \iff$ There do not exist $a, b, c$ such that $a > b > c$, $f(a) < f(b) < f(c)$.

For bijective functions in general, we shall prove $v \le u \le 2v$, with $u = v$ only for the identity and $u = 2v$ if and only if there do not exist $a > b > c$ such that $f(a) < f(b) < f(c)$. We argue by induction on $u$.
If $u = 0$, $\sum_{k=1}^{n} |f(k) - k| = 0$, $|f(k) - k| = 0$ for all $k$, $f(k) = k$ and $f$ is the identity. In this case, $v = 0$, $v = u = 2v$ and there do not exist $a > b > c$ with $f(a) < f(b) < f(c)$. This satisfies the result.

Now, suppose that the statement is true for $0 \le u < t$, and we have a function $f$ with $u = t$. $\sum_{k=1}^{n} f(k) - k = \sum_{k=1}^{n} f(k) - \sum_{k=1}^{n} k = \sum_{k=1}^{n} k - \sum_{k=1}^{n} k = 0$. Since $u = \sum_{k=1}^{n} |f(k) - k| \ne 0$, there exists $k$ with $f(k) - k < 0$ (that is, $f(k) < k$), and $k$ with $f(k) - k > 0$. Let $x$ be the smallest value of $k$ with $f(k) < k$. $f(f(x)) \ne f(x)$ because if it was equal, then $f(x) = x$. Since $f(x) < x$, and by definition of $x$, $f(f(x)) > f(x)$. There are values of $k$ less than $x$ with $f(k) > k$. Let $y$ be the greatest one.

We define $\bar{k}$ as follows: $\bar{x} = y$, $\bar{y} = x$ and $\bar{k} = k$ for the rest of the values. We define $\tilde{f}$ as $\tilde{f}(k) = f(\bar{k})$, and define $\tilde{u}$ and $\tilde{v}$ analogously to $u$ and $v$ for $f$. Let $z = x - y$.
For all $k$ with $y < k < x$, $f(k)$ is not less than $k$ by definition of $x$, nor greater than $k$ by definition of $y$. Therefore, $f(k) = k$. If $y < f(x) < x$, then $f(f(x)) = f(x)$, impossible. Hence, $f(x) \le y$. In the same way, $f(y) \ge x$.
$$u - \tilde{u} = \sum_{k=1}^{n} |f(\bar{k}) - \bar{k}| - \sum_{k=1}^{n} |\tilde{f}(k) - k| = |f(x) - x| - |\tilde{f}(y) - y| + |f(y) - y| - |\tilde{f}(x) - x| = x - y - y + x = 2z.$$
$\tilde{u} < u = t$, so by induction hypothesis $\tilde{v} \le \tilde{u} \le 2\tilde{v}$.

Let us find the value of $v - \tilde{v}$, by finding the cases when $(\bar{a}, \bar{b})$ is included in $v$ and $(a, b)$ is not included in $\tilde{v}$, and vice versa. The condition for the first case can be written as $\bar{a} > \bar{b}$, $f(\bar{a}) < f(\bar{b})$ and $a < b$. It is clear that one of the terms must be $x$ or $y$. $a = y$ and $b = x$ satisfies this. If only one of the terms appears and it is $a$, then $\bar{a} > \bar{b} = b > a$, $a = y$ and $x > b > y$. All the values of $b$ in this interval satisfy the condition because $f(y) \ge x > b = f(b)$. Likewise, if the term that appears is $b$, then $b = x$ and $x > a > y$ satisfies the conditions. We can check that there are no pairs $(a, b)$ counted in $\tilde{v}$ but $(\bar{a}, \bar{b})$ not counting in $v$. $v - \tilde{v} = 1 + 2(z - 1) = 2z - 1$.

Using the previous results, $v = \tilde{v} + 2z - 1 \le \tilde{u} + 2z - 1 < \tilde{u} + 2z = u \le 2\tilde{v} + 2z \le 2\tilde{v} + 2(2z - 1) = 2v$. This proves the inequality.

All that remains is finding when $u = 2v$ holds. This happens whenever $\tilde{u} = 2\tilde{v}$ and $z = 1$. If $z > 1$, $x > y + 1 > y$ and $f(x) \le y < y + 1 = f(y + 1) < x \le f(y)$. We can therefore suppose $z = 1$. We need to prove that there exist $a > b > c$ with $f(a) < f(b) < f(c)$ if and only if there exist $a > b > c$ with $\tilde{f}(a) < \tilde{f}(b) < \tilde{f}(c)$. $f(\bar{a}) < f(\bar{b}) < f(\bar{c}) \iff \tilde{f}(a) < \tilde{f}(b) < \tilde{f}(c)$. If two elements of $\{a, b, c\}$ are neither $x$ nor $y$, for example $a$ and $c$, then $\bar{a} = a$, $\bar{c} = c$ and since $x = y + 1$, $a > x > c \iff a > y > c$. If both $x$ and $y$ appear, they cannot be $a$ and $c$ because $x$ and $y$ are consecutive integers. Hence, one of them is $b$, for example $x$. $a > x > y$ and $f(a) < f(x) < f(y)$. As $f(x) < x$, there are more values of $k$ with $k < x$ and $f(k) > f(x)$ than $k > x$ with $f(k) < f(x)$. Since $a$ is an example of the latter, there is $d$ not equal to $y$ with $d < x$ and $f(d) > f(x)$, and therefore $a > x > d$ and $f(a) < f(x) < f(d)$, where $y$ does not appear. We reduced the problem to the previous case. The same argument works if $\tilde{f}(a) < \tilde{f}(x) < \tilde{f}(y)$ or if $b = y$, and we are done.