How find this minimum of the value $f(1)+f(2)+\cdots+f(100)$

Solution 1:

Let $n$ be the largest number such that $f(n)\ne 100$. By property (2), there does not exist an $i$ such that $f(i)=n$; by property (1), the graph of $f$ cannot "cross" $n$. Thus $f$ has these two properties:

(i) $f(A)\subseteq[n+1,100]$

(ii) $f([n+1,100]) = \{100\}$

Furthermore, any function having properties (i) and (ii) has property (2).

Of all functions satisfying properties (1), (i), and (ii), the smallest (pointwise, and therefore also in the sense of $\sum_i f(i)$) will have a graph that looks either like

100             * * * * *
              *
            *
          *
        *
      *
    *




    1 2 3 ... n n+1 ... 100

or like

100                   * * * * * *
                    *
                  *
                *
              *
n+1 * * * * *



    1 2 3    ...    n n+1 ... 100

For functions of these types, the value of $\sum_{i=1}^{100} f(i)$ can be computed explicitly as a function of $n$; it'll turn out to be piecewise quadratic in $n$, so you can find the minimum using standard techniques from high school algebra.

Solution 2:

As Test Observed, here is a start, the solution is incomplete.

First observe that by repeatedly applying $(1)$ you get the following:

If $1 \leq i < j < 100$ then

$$\left|f(i)-f(j)\right| \leq j-i \,.$$

Now, if $f(i)=j$ we either have $j =100$ or, by the above

$$ 100-j =|f(i)-f(j) | \leq |j-i| \,.$$

This implies that

$$100-j \leq i-j \, \mbox{or} \, 100-j \leq j-i \,.$$

Therefore , for all $1 \leq i \leq 99$ we have

$$ f(i) \geq \frac{100+i}{2}$$

As $f(i)$ is an integer, for all $1 \leq i\leq 99$ we have

$$f(i) \geq [ \frac{100+i}{2} ] \,,$$ where $[]$ denotes rounded up.

Next, let $f(1)=a$ with $51 \leq a \leq 100$.

I would cover the case $f(1)=100$ separately, lets look at the case $51 \leq a \leq 99$.

The solution can be completed in a very ugly way, by covering all the cases for $f(1)$, but there should be a simpler solution.

Solution 3:

Claim: to achieve the minimum, f(n) is a non decreasing function. Suppose not, take the natural construction $f^*(n)$ where we smooth out the decreasing part, show that it satisfies the conditions and has a smaller sum.

Claim: Suppose that The image of $f(n)$ consists of $k$ elements. Then, because we have a non decreasing function, we see that the minimum sum occurs when we have $f(1)=\ldots=f(100-2k+2)=100-k+1, f(100-2k +j)=100-k+j-1$ for j from 3 to k and $f(100-k+1)=\ldots=f(100)=100$.

It remains to verify that the minimum sum is achieved at $k=34$ This is easily done n