IMO 2015 warm up problem

Question

I get this problem from IMO 2015 facebook page. Let $x_i$ be positive integers for $i=1,2,...,11$. If $x_i+x_{i+1}\geq 100$, $|x_i-x_{i+1}|\geq 20$ for $i=1,2,...,10$. And $x_{11}+x_{1}\geq 100$, $|x_{11}-x_1|\geq 20$. What is the minimum possible value of $\sum_{i=1}^{11}x_i$ ? Thanks for solutions.

Answer 1

The minimum sum is 580. Imagine that $x_1, x_2, ..., x_{11}$ are placed around a circle. By summing consecutive pairs starting at $x_{j+1}$ we notice that $\sum x_i \geq 500 + x_j$. So letting $x^* = \max_i\{x_i\}$ we have

$$ \sum x_i \geq 500 + x^* $$

First we note that $x^* \geq 60$ because if not, its neighbors cannot possibly satisfy the constraints. Next we prove that $x^* \geq 80$. Suppose NOT and WLOG let $x_1 = x^*$. By the constraints and the bounds on $x^*$, we find

$$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) \;\;\;\;\;\;\;\;$$

a contradiction (the two $\implies$ are fairly obvious so I leave the gritty details to you). So we've shown that $\sum x_i \geq 580$. The assignment 80, 60, 40, 60, 40, 60, 40, 60, 40, 60, 40 proves that the bound is tight.