Find maximum value of number $a$ such that for any arrangement of numbers $1,2,\ldots ,10$ on a circle, we can find three consecutive numbers such their sum bigger or equal than $a$.
Problem
Source: Bosnia and Herzegovina 2011
Tags: combinatorics proposed, combinatorics
17.05.2011 15:02
We will prove that the maximum value of $a$ is larger than or equal to 18. First, define $x_1, x_2, \cdots, x_{10}$ to be the numbers on the circle consecutively, $x_{11} = x_1$, $x_{12} = x_2$, and $y_k = x_k + x_{k+1} + x_{k+2}$ for $1 \le k \le 10$. Note that since $\sum x_i = 55$, $\sum y_i = 165$, so that there exists some $y_i$ such that $y_i \ge 17$. Then $a \ge 17$. Let us assume the contrary; that is, $a \le 17$. So since $a \ge 17$, $a$ must be equal to 17, so all $y_i$ must be less than or equal to 17. Note that $y_i$ and $y_{i+1}$ can't be equal for any $1 \le i \le 10$ (assume $y_{11} = y_1$), because if they are equal, then $x_i$ and $x_{i+3}$ are equal (assume $x_{13} = x_3$). So there are at most five $y_i$ which are equal to 17; WLOG assume $y_1 = y_3 = y_5 = y_7 = y_9 = 17$. This causes $y_2, y_4, y_6, y_8, y_{10} \le 16$. However, since $\sum y_i = 165$, $y_2 + y_4 + y_6 + y_8 + y_{10} = 80$, so $y_2 = y_4 = y_6 = y_8 = y_{10} = 16$. Now, note that $x_1 = x_4 + 1$, and $x_4 = x_7 - 1$ by comparing $y_1$ against $y_2$ and $y_4$ against $y_5$. This means $x_1 = x_7$, contradiction. So $a$ cannot be equal to 17, contradiction. Now, this leaves us with the necessity of the proof that $a \le 18$. Note the following arrangement: 10 1 7 9 2 6 4 8 3 5 No three consecutive numbers has a sum of larger than 18, so $a \le 18$. So the maximum value of $a$ is $\boxed{18}$.
01.07.2011 02:41
There is a much simpler argument for $a\geq 18$. The other nine numbers than $1$ form three groups of three adjacent numbers each, of total sum $54=3\cdot 18$, so (at least) one of the grup sums to (at least) $18$.
11.07.2011 17:40
Yes, mavropnevma, that was official solution. My was same as the one of chaotic_iak.
15.12.2013 04:50
RaleD wrote: Find maximum value of number $a$ such that for any arrangement of numbers $1,2,\ldots ,10$ on a circle, we can find three consecutive numbers such their sum bigger or equal than $a$. Find maximum value of number $a$ such that for any arrangement of numbers $1,2,\ldots ,10$ on a line, we can find three consecutive numbers such their sum bigger or equal than $a$ ?.