Encontrar el máximo de la suma de $\sum_{k=1}^{n}(f(f(k))-f(k))$

Question

Deje $f:\{1,2,3,\cdots,n\}\to \{1,2,3,\cdots,n\}$ tal que $$f(1)\le f(2)\le\cdots\le f(n)$$ encontrar el máximo de la $$\sum_{k=1}^{n}(f(f(k))-f(k))$$

Answer 1

A mi mejor esfuerzo:

Deje $m=\lceil \frac{n+1}{2}\rceil$. Por lo $m=\frac{n+1}{2}$ por extraño $n$, e $m=\frac{n+2}{2}$ incluso $n$.

A continuación, vamos a $f(k)=m$$1 \le k \lt m$$f(k)=n$$m \le k \le n$. En particular,$f(m)=f(n)=n$.

En este caso, $f(f(k))=n$ todos los $k$ $\displaystyle \sum_{k=1}^n (f(f(k))-f(k)) = (m-1)(n-m).$

Por extraño $n$ esto da $\displaystyle \sum_{k=1}^n (f(f(k))-f(k)) = \left(\frac{n=1}{2}\right)^2 = \frac{n^2}{4}-\frac{n}{2}+\frac14.$

Incluso para $n$ esto da $\displaystyle \sum_{k=1}^n (f(f(k))-f(k)) = \frac{n}{2} \times \frac{n-2}{2}= \frac{n^2}{4}-\frac{n}{2}.$

Answer 2

Esto no es una prueba, pero supongo que este puede ser el máximo.

Asumir $$f(k)=\min (k+d,n)\quad(d\ge1)$$ Entonces \begin{align} &\sum_{k=1}^n (f(f(k))-f(k))\\ &=\sum_{k=1}^n f(f(k))-\sum_{k=1}^nf(k)\\ &=\sum_{k=1}^n f(\min (k+d,n))-\sum_{k=1}^n\min (k+d,n))\\ &=\sum_{k=1}^n \min(\min (k+d,n)+d,n)-\sum_{k=1}^n\min (k+d,n))\\ &=\sum_{k=1}^{n-d} \min(k+2d,n)+\sum_{k=n-d+1}^{n}\min(n+d,n)-\sum_{k=1}^{n-d} (k+d)-\sum_{k=n-d+1}^{n}n\\ &=\sum_{k=1}^{n-2d} (k+2d)+\sum_{k=n-2d+1}^{n} n-\sum_{k=1}^{n-d} (k+d)-\sum_{k=n-d+1}^{n}n\\ &=\sum_{k=1}^{n-2d} d+\sum_{k=n-2d+1}^{n-d}(n-(k+d))\\ &=(n-2d)d+d(n-d)-\sum_{k=1}^{n-d}k+\sum_{k=1}^{n-2d+1}k\\ &=2nd-3d^2-\frac{(n-d)(n-d+1)}2+\frac{(n-2d)(n-2d+1)}2\\ &=\frac{(2n-1)d-3d^2}{2}\\ &=\frac{-3\left(d-\left(\frac{2n-1}{6}\right)\right)^2+3\left(\frac{2n-1}{6}\right)^2}{2}\\ &\le \frac{(2n-1)\lfloor\frac{2n-1}{6}\rfloor-3\lfloor\frac{2n-1}{6}\rfloor^2}{2} \end{align}