Austria competition problems, 2010

Note first that the function $f_n(x)$ satisfies $f_n(x) = f_n(n+1-x)$:
$$f_n(n+1-x) = \sum_{k=1}^{n} |n+1-x-k| = \sum_{k=1}^{n} |x - (n+1-k)| = \sum_{k=1}^{n} |x-k| = f_n(x)$$
by reversing the order of summation. Let us first consider the case $x < 1$: then, $x-k < 0$ for every $k \ge 1$ and thus
$$f_n(x) = \sum_{k=1}^{n} (k-x) = \frac{n(n+1)}{2} - nx > \frac{n(n+1)}{2} - n = \frac{n(n-1)}{2} \ge \frac{10 \cdot 9}{2} = 45 > 41,$$
so this case can be excluded. By symmetry (identity above), we can exclude $x > n$ as well. Thus we are left with $1 \le x \le n$. Suppose that $x \in [\ell, \ell + 1]$ for some integer $\ell$ with $1 \le \ell \le n - 1$. Then $x - k \le 0$ for $k \ge \ell + 1$ and $x - k \ge 0$ for $k \le \ell$, and we obtain
$$\begin{aligned} f_n(x) &= \sum_{k=1}^{\ell} (x-k) + \sum_{k=\ell+1}^{n} (k-x) = \ell x - \frac{\ell(\ell+1)}{2} + \frac{(n-\ell)(n+\ell+1)}{2} - (n-\ell)x \\ &= \frac{n(n+1)}{2} - \ell(\ell+1) + (2\ell-n)x. \end{aligned}$$
This shows that $f_n(x)$ is strictly decreasing on $[\ell, \ell + 1]$ if $\ell < \frac{n}{2}$, constant on $[\frac{n}{2}, \frac{n}{2} + 1]$ (if $n$ is even) and strictly increasing on $[\ell, \ell + 1]$ if $\ell > \frac{n}{2}$. We conclude:
* If $n$ is even, then $f_n(x)$ is strictly decreasing on $[1, \frac{n}{2}]$, constant on $[\frac{n}{2}, \frac{n}{2} + 1]$ and strictly increasing on $[\frac{n}{2} + 1, n]$.
* If $n$ is odd, then $f_n(x)$ is strictly decreasing on $[1, \frac{n+1}{2}]$ and strictly increasing on $[\frac{n+1}{2}, n]$.
We see that the minimum of $f_n(x)$ is always attained at $m = \lfloor \frac{n+1}{2} \rfloor$. Now we can complete squares in the above to obtain
$$\begin{aligned} f_n(m) &= \frac{n(n+1)}{2} - m(m+1) + (2m-n)m = \frac{n(n+1)}{2} + m^2 - (n+1)m \\ &= \frac{n(n+1)}{2} + \left(m - \frac{n+1}{2}\right)^2 - \left(\frac{n+1}{2}\right)^2 \ge \frac{n(n+1)}{2} - \left(\frac{n+1}{2}\right)^2 = \frac{n^2-1}{4}. \end{aligned}$$
If $n \ge 13$, then this implies $f_n(x) \ge f_n(m) \ge \frac{13^2-1}{4} = 42 > 41$ for all $x$, so that there is no solution. It remains to consider $n \in \{10, 11, 12\}$.
* For $n = 10$, we obtain from above that
$$f_{10}\left(\frac{3}{2}\right) = 55 - 2 - 8 \cdot \frac{3}{2} = 41$$
and by the symmetry property $f_{10}\left(\frac{19}{2}\right) = 41$. In view of our monotonicity considerations, $f_{10}(x) \ge 41$ for $x \le \frac{3}{2}$ and $x \ge \frac{19}{2}$ and $f_{10}(x) < 41$ on the remaining interval. So we find that the solution set in this case is $\left(\frac{3}{2}, \frac{19}{2}\right)$.
* For $n = 11$, we have
$$f_{11}\left(\frac{19}{7}\right) = 66 - 6 - 7 \cdot \frac{19}{7} = 41$$
and $f_{11}\left(\frac{65}{7}\right) = 41$ by symmetry. The same argument as before shows that the solution set is $\left(\frac{19}{7}, \frac{65}{7}\right)$ in this case.
* For $n = 12$, we have
$$f_{12}\left(\frac{17}{4}\right) = 78 - 20 - 4 \cdot \frac{17}{4} = 41$$
and $f_{12}\left(\frac{35}{4}\right) = 41$ by symmetry. Hence we obtain the solution set $\left(\frac{17}{4}, \frac{35}{4}\right)$ in this case.
Let us summarize the solutions:
* $\frac{3}{2} < x < \frac{19}{2}$ for $n = 10$,
* $\frac{19}{7} < x < \frac{65}{7}$ for $n = 11$,
* $\frac{17}{4} < x < \frac{35}{4}$ for $n = 12$,
* no solutions if $n \ge 13$.