На окружности в случайном порядке были расположены натуральные числа от $1$ до $16$. Над каждой парой соседних чисел написали модуль их разности, после чего исходные числа стёрли и посчитали сумму $s$ оставшихся модулей разностей. а) Могло ли оказаться, что $s=40$? б) Могло ли оказаться, что $s=41$? в) Найдите максимально возможное значение $s$.
а) Да, могло. Приведём пример. Пусть по часовой стрелке числа записаны в следующем порядке: $1$; $2$; $3$; $4$; $5$; $6$; $7$; $8$; $9$; $10$; $16$; $11$; $15$; $13$; $14$; $12$. Сумма модулей указанных разностей равна $40$. б) Нет, не могло. Пусть изначально на доске в порядке следования по часовой стрелке записаны числа $a_1$, $a_2$, $a_3$, … , $a_{16}$ — переставленные натуральные числа от $1$ до $16$. Заметим, что для произвольных натуральных чисел $m$ и $n$ числа $m-n$ и $n-m$ имеют одинаковую чётность, а значит $|m-n|$ имеет ту же чётность, что $m-n$. Но тогда сумма $|a_1-a_2|+|a_2-a_3|+|a_3-a_4|+ … +|a_{15}-a_{16}|+|a_{16}-a_1|$ будет
нечётной только в том случае, если сумма
$(a_1-a_2)+(a_2-a_3)+(a_3-a_4)+ … +(a_{15}-a_{16})+(a_{16}-a_1)$ будет нечётной, но последняя сумма равна $0$, следовательно, чётна. Отсюда сумма $|a_1-a_2|+|a_2-a_3|+|a_3-a_4|+ … +|a_{15}-a_{16}|+|a_{16}-a_1|$ чётна и не может равняться $41$. в) Заметим, что $|a_1-a_2|+|a_2-a_3|+|a_3-a_4|+ … +|a_{15}-a_{16}|+|a_{16}-a_1|=$
$=(x_1+x_2+x_3+… +x_{16})-(y_1+y_2+y_3+… y_{16})$. Каждый модуль $|a_i-a_{i+1}|$ ($i=1, 2, … 15$) представлен в виде, $x_i-y_i$, где $x_1$ — большее из чисел $a_i$ и $a_{i+1}$, $y_i$ — меньшее из них. Аналогично $|a_{16}-a_1|=x_{16}-y_{16}$. Причём каждое $a_k$ встречается среди чисел $x_1$, $x_2$, …, $x_{16}$, $y_1$, $y_2$, …, $y_{16}$ ровно $2$ раза. Тогда $x_1+x_2+x_3+… +x_{16}⩽ 16+16+15+15+… +9+9=200$, а $y_1+y_2+y_3+… +y_{16}⩾ 1+1+2+2+… +8+8=72$. Отсюда $(x_1+x_2+x_3+… +x_{16})-(y_1+y_2+y_3+… +y_{16})⩽200-72=128$, то есть сумма записанных модулей разностей не превышает $128$. Приведём пример, в котором указанная сумма равна $128$. Пусть на доске изначально числа в следующем порядке (по часовой стрелке): $1$; $16$; $2$; $15$; $3$; $14$; $4$; $13$; $5$; $12$; $6$; $11$; $7$; $10$; $8$; $9$. Тогда $|1-16|+|16-2|+|2-15|+|15-3|+|3-14|+|14-4|+|4-13|+$
$+|13-5|+|5-12|+|12-6|+|6-11|+|11-7|+|7-10|+|10-8|+|8-9|+$
$+|9-1|=128$.
Ответ: а)да; б)нет; в)128