Cómo encontrar este mínimo del valor $f(1)+f(2)+\cdots+f(100)$

Question

Dar el conjunto de enteros positivos $A=\{1,2,3,\cdots,100\}$ y definir la función $f:A\to A$ y

(1):tal para cualquier $1\le i\le 99$ ,tienen $$|f(i)-f(i+1)|\le 1$$ (2): para cualquier $1\le i\le 100$ ,tienen $$f(f(i))=100$$

encontrar el mínimo del valor $$f(1)+f(2)+f(3)+f(4)+\cdots+f(99)+f(100)$$

Quizás este es un buen problema, y quiero usar $|f(i)-f(i+1)|\le 1$ Pero no puedo. Gracias.

Ahora se dice que esta respuesta es 8350

Answer 1

Dejemos que $n$ sea el mayor número tal que $f(n)\ne 100$ . Por la propiedad (2), no existe un $i$ tal que $f(i)=n$ por la propiedad (1), la gráfica de $f$ no puede "cruzar" $n$ . Así, $f$ tiene estas dos propiedades:

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

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

Además, cualquier función que tenga las propiedades (i) y (ii) tiene la propiedad (2).

De todas las funciones que satisfacen las propiedades (1), (i) y (ii), la más pequeña (puntualmente, y por tanto también en el sentido de $\sum_i f(i)$ ) tendrá un gráfico que se parece a

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

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

o como

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

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

Para las funciones de este tipo, el valor de $\sum_{i=1}^{100} f(i)$ puede calcularse explícitamente en función de $n$ ; resultará ser cuadrática a trozos en $n$ Así que puedes encontrar el mínimo usando las técnicas estándar del álgebra de la escuela secundaria.

Answer 2

Como prueba observada, aquí hay un comienzo, la solución es incompleta.

En primer lugar, observe que al aplicar repetidamente $(1)$ se obtiene lo siguiente:

Si $1 \leq i < j < 100$ entonces

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

Ahora bien, si $f(i)=j$ o bien tenemos $j =100$ o, por lo anterior

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

Esto implica que

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

Por lo tanto, para todos los $1 \leq i \leq 99$ tenemos

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

Como $f(i)$ es un número entero, para todo $1 \leq i\leq 99$ tenemos

$$f(i) \geq [ \frac{100+i}{2} ] \,,$$ donde $[]$ indica que se ha redondeado.

A continuación, dejemos que $f(1)=a$ con $51 \leq a \leq 100$ .

Yo cubriría el caso $f(1)=100$ Por separado, veamos el caso $51 \leq a \leq 99$ .

La solución se puede completar de una manera muy fea, cubriendo todos los casos para $f(1)$ pero debería haber una solución más sencilla.

Answer 3

Afirmación: para alcanzar el mínimo, f(n) es una función no decreciente. Supongamos que no, tomemos la construcción natural $f^*(n)$ donde suavizamos la parte decreciente, mostramos que satisface las condiciones y tiene una suma menor.

Afirmación: Supongamos que La imagen de $f(n)$ consiste en $k$ elementos. Entonces, como tenemos una función no decreciente, vemos que la suma mínima se produce cuando tenemos $f(1)=\ldots=f(100-2k+2)=100-k+1, f(100-2k +j)=100-k+j-1$ para j de 3 a k y $f(100-k+1)=\ldots=f(100)=100$ .

Queda por comprobar que la suma mínima se alcanza en $k=34$ Esto se hace fácilmente n

Answer 4

(Editado)

Mi intento:

$$ f(x)=\left\{ \begin{array}{ll} 67,& \mbox{if } 1\le x\le 34;\\ 33+x,& \mbox{if } 34\le x \le 67;\\ 100, &\mbox{if } 67\le x \le 100.\end{array} \right. $$

Entonces $$f(1)+f(2)+...+f(100)=34\cdot 67 + (68+69+...+99) + 34\cdot 100 =2278 + 2672 + 3400 = \large{8350}.$$

---

Mi enfoque:

Denote $A_{100}$ es el conjunto de $a\in A$ que $f(a)=100$ .

Si $A_{100}=A$ no es la solución óptima ( $f(x)\equiv 100$ ).

Entonces $A_{100}$ está "acotado" con el conjunto $A_{99}$ (conjunto de tales $a\in A$ que $f(a)=99$ ). Entonces (2) $\implies f(99)=100$ .

Pero si $A_{99} \bigcup A_{100} = A$ entonces tampoco es una solución óptima.

Siguiente paso: entonces $A_{99}$ está "acotado" con el conjunto $A_{98}$ (conjunto de tales $a$ ...). Entonces (2) $\implies f(98)=100$ .

Y así sucesivamente...