Tengo este problema desde la OMI 2015 facebook de la página. Deje $x_i$ ser enteros positivos para $i=1,2,...,11$. Si $x_i+x_{i+1}\geq 100$, $|x_i-x_{i+1}|\geq 20$ para $i=1,2,...,10$. Y $x_{11}+x_{1}\geq 100$, $|x_{11}-x_1|\geq 20$. ¿Cuál es el mínimo valor posible de $\sum_{i=1}^{11}x_i$ ? Gracias por las soluciones.
Respuesta
¿Demasiados anuncios?
Andrew Szymczak
Puntos
842
El importe mínimo es de 580. Imagina que $x_1, x_2, ..., x_{11}$ están ubicadas alrededor de un círculo. Sumando pares consecutivos comenzando en $x_{j+1}$ nos damos cuenta de que $\sum x_i \geq 500 + x_j$. Por lo tanto, dejar $x^* = \max_i\{x_i\}$ hemos
$$ \sum x_i \geq 500 + x^* $$
Primero tomamos nota de que $x^* \geq 60$ porque si no, la de sus vecinos no pueden satisfacer las restricciones. Lo siguiente que queremos demostrar que $x^* \geq 80$. Supongo que NO y WLOG deje $x_1 = x^*$. Por las restricciones y los límites en las $x^*$, nos encontramos con
$$x_1 \in [60,80) \implies x_2 \in (20,60) \implies \\ x_3 \in [60,80) \implies \;\;\;\;\;\;\;\; ... \;\;\;\;\;\;\;\implies \\ x_{11} \in [60,80) \implies x_1 \in (20,60) \;\;\;\;\;\;\;\;$$
una contradicción (los dos $\implies$ son bastante obvios así que os dejo los detalles más irrelevantes). Hemos demostrado que $\sum x_i \geq 580$. La asignación de 80, 60, 40, 60, 40, 60, 40, 60, 40, 60, 40 la prueba de que el obligado es apretado.
