4
$\begingroup$

A seemingly interesting (easy?) problem came to mind and I thought it would be nice to ask your opinion about it.

Suppose we are going to arrange numbers $0$ to $n$ in a row in such a way that the sum of the difference between adjacent numbers is max. How could we accomplish this? How could we determine the maximum sum of the difference? How about the minimum?

As an example let us take the numbers $0,1,2,3,4$. Let us look at some arrangements:

$0,1,2,3,4$; the difference between the adjacent numbers are $1,1,1,1$ so the sum is $4$

$1,3,4,0,2$; the difference between the adjacent numbers are $2,1,4,2$ so the sum is $9$

$1,4,0,3,2$; the difference between the adjacent numbers are $3,4,3,1$ so the sum is $11$

$3,0,4,1,2$; the difference between the adjacent numbers are $3,4,3,1$ so the sum is $11$

I figured that the arrangement that will give us the minimum sum is the arrangement $1,2,3,...,n$ because all the difference would just be $1$ and their sum is $n-1$.

I think the maximum sum can be attained by arranging the numbers in the following way:

Place the number $n$ between $0$ and $1$. Then place $n-1$ next to $0$ and $n-2$ next to $1$ and so on.

An additional question, if we already know the minimum and maximum would it be possible to always get an arrangement that will give a sum for all the values between the minimum and the maximum? I tried it with $0,1,2,3$ and I was able to find arrangements for all the values between $3$ and $7$.

Maybe this problem has been asked before but I can't find it on the net. Any ideas? Thanks!

$\endgroup$
  • 2
    $\begingroup$ For the sets {0,...,n}, the sequence of maximal sums begins (with n=2) 1,3,7,11,17,23,31,39. This appears to be oeis.org/A047838 though I cannot find a reference for your problem. A small variation on your problem is perhaps more common: arrange the numbers in a circle, so you have one more difference. This is related to dartboard design, of which there are a few papers. $\endgroup$ – Matthew Conroy Dec 19 '13 at 5:44
  • 1
    $\begingroup$ For example, jstor.org/discover/10.2307/… $\endgroup$ – Matthew Conroy Dec 19 '13 at 5:45
  • $\begingroup$ Thank you for the links. I'm trying to figure out now why the max of the sum of the difference coincides with the sequence 1,3,7,11,17,.. $\endgroup$ – chowching Dec 19 '13 at 6:55
  • 1
    $\begingroup$ A pretty obvious note: The sequence's terms (given above) increase by: $2, 4, 4, 6, 6, 8, 8, 10, 10\ldots$ suggesting a pattern to compute this number for general $n$. Of course, proving it holds is a different story. $\endgroup$ – Benjamin Dickman Dec 19 '13 at 8:47
1
$\begingroup$

I have an idea how to obtain an upper bound which seems to be good. We have to estimate from above the sum $S=\sum_{i=1}^n |a_i-a_{i-1}|$ where the sequence $a_0,\dots, a_n$ is a permutation of the sequence $0,1,\dots,n$. When we open the moduli in the expression for $S$, we obtain $S=\sum_{i=0}^n\varepsilon_i a_i$, where $\sum_{i=0}^n\varepsilon_i=0$ and $\varepsilon_i\in\{-1,1\}$ for $i=0$ or $i=n$ and $\varepsilon_i\in\{-2,0,2\}$ for $1\le i\le n-1$. Suppose that $n=2k+1$ is odd. Now it seems to be true and easily provable that $S$ have the maximum $(n-1)^2/2-1$ when the $\varepsilon$-coefficients at the numbers $0,1,\dots,k-1$ are “-2”, at $k+2,k+3,\dots,n$ are “2”, at $k$ is “-1” and at $k+1$ is “1”. The case when $n$ is even can be considered similarly.

$\endgroup$
  • $\begingroup$ Thanks for taking the time to look at this problem. How do we show that $\lfloor{\frac{n^2}{2}}\rfloor -1$ is max? And well, shouldn't we be using $n+1$ instead of $n$ in $\lfloor{\frac{n^2}{2}}\rfloor +1$ because we started with zero? Thanks! :) $\endgroup$ – chowching Dec 20 '13 at 17:05
  • $\begingroup$ @chowching Thank you for your attentiveness. I tried to corrected the formula for the maximum of $S$ taking into account that we started with zero. $\endgroup$ – Alex Ravsky Dec 21 '13 at 1:02
  • $\begingroup$ @chowching I think that to show the maximality of the construction it is helpful to wrote $S=\sum_{i=0}^n\varepsilon_i a_i$ as $\sum_{i=0}^n\delta_i i$. Then for a construction with a maximal $S$ the sequence $\delta_i$ should be non-decreasing, because in an other case we can swap $\delta_i$ and $\delta_j$ and obtain a bigger value for $S$. $\endgroup$ – Alex Ravsky Dec 21 '13 at 1:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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