1
$\begingroup$

Suppose that a team of $ n $ players (numbered from 1 to $ n $) sit around a circular table and there are their numbers on their T-shirts.

Let $ a_1,a_2,..., a_n $ be the sequence of numbers around the table and so $ a_n $ sits beside $ a_1$. What is the maximum value of $|a_1-a_n|+\sum_{k=1}^{n-1 }|a_{k+1}-a_k|$?

As we checked the maximum value is equal to $ n^2/2$ for even $ n $ but we can not prove it. Could you help us? Thanks in advance

$\endgroup$
2
  • 2
    $\begingroup$ I just verified this conjecture up to n = 22 by solving for the maximum as a Mixed Integer Linear Programming (MILP) problem. $\endgroup$ Mar 17, 2020 at 17:48
  • $\begingroup$ Thanks for your help $\endgroup$
    – khers
    Mar 17, 2020 at 18:23

1 Answer 1

2
$\begingroup$

For $n$ even let $\{b_{2i-1}, b_{2i}\} = \{a_{2i-1}, a_{2i}\}$ with $b_{2i-1} < b_{2i}$. Then $\{b_1, \ldots, b_n\} = \{1, \ldots, n\}$ and $$ \begin{align*} \sum_{i=1}^{n/2} |a_{2i-1} - a_{2i}| &= \sum_{i=0}^{n/2} (b_{2i} - b_{2i-1}) \\ &= \sum_{i=1}^{n/2} b_{2i} - \sum_{i=0}^{n/2} b_{2i-1} \\ &\leq \sum_{i=0}^{n/2} (n/2+i) - \sum_{i=1}^{n/2} i = n^2/4, \end{align*} $$ by taking the even-indexed $b_i$ to be as large as possible and the odd-indexed $b_i$ to be as small as possible. Similarly, $$ \sum_{i=1}^{n/2} |a_{2i} - a_{2i+1}| \leq n^2/4, $$ with indices taken mod $n$. Summing these inequalities gives the upper bound, and you can get a matching lower bound by using the larger and smaller halves of $\{1, \ldots, n\}$ in the odd- and even-indexed positions respectively.

$\endgroup$
2
  • $\begingroup$ An equivalent, maybe clearer definition: $b_{2i-1}=\min(a_{2i-1},a_{2i})$, $b_{2i}=\max(a_{2i-1},a_{2i})$. $\endgroup$
    – user44143
    Mar 17, 2020 at 21:05
  • $\begingroup$ Thanks so much for your nice solution! $\endgroup$
    – khers
    Mar 18, 2020 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.