Spring 2016, problem 9

The numbers $1, 2, \dots , n$ are written around a circle in some order. What is the smallest and largest possible sum of the absolute differences of adjacent numbers?

Comments

1 year ago

The maximum is $\lfloor \frac{n^2}{2} \rfloor$. The minimum is $2 (n - 1)$.

Proof of the maximality part:

For a circular arrangement of $1..n$ call the sum of the absolute differences of neighbours the value of the arrangement. For $a, b \in \left \{1..n \right \}$ write $a \rightarrow b$, if $b$ is the right side neighbour of $a$.

If $n$ is even, call the numbers $\frac{n}{2} .. n$ the large numbers. Call the rest small. If $n$ is odd call the numbers $\frac{n + 3}{2} .. n $ the large numbers. Call $\frac{n + 1}{2}$ the middle number. Call the rest small.

The value $v$ of the arrangement is given by:

$v := \sum_{a \rightarrow b} \left [max(a,b) - min(a,b) \right ] = \sum_{a \rightarrow b} max(a,b) - \sum_{a \rightarrow b} min(a,b)$.

Each of the two sums in the last expression is a sum of $n$ numbers in the range $1..n$, none of which occur more than twice in any of the sums. The value $v$ is clearly no larger than $m$, given by: $m := \left [ n + n + (n -1) + (n-1) + ... \right ] - \left [1 +1 + 2 + 2 + 3 + 3 ... \right ]$, where the first and the second bracket contain $n$ terms each. By a simple calculation $m = \lfloor \frac{n^2}{2} \rfloor$. But the value $m$ is indeed attained:

For $n$ even arrange the numbers like:

large $\rightarrow$ small $\rightarrow$ large $\rightarrow$ small ... $\rightarrow$ large$\rightarrow$ small

For $n$ odd arrange like:

middle $\rightarrow$ large $\rightarrow$ small $\rightarrow$ large $\rightarrow$ small ... $\rightarrow$ large$\rightarrow$ small. Done.

Proof of the minimality part:

Proof by induction over $n$: The induction start is trivial. So assume, that the minimum value for arrangements of numbers in $1..n$ is given by $m_n := 2 (n -1)$. Consider a minimum-value arrangement $A_{n+1}$ of the numbers $1..(n+1)$. with value $v_{n+1}$. Now take away the number $n+1$ from $A_ {n+1}$. You get an arrangement $A_n$ of the numers $1..n$, with value $v_{n}$. By an easy calculation $v _n \leq v_{n+1} -2$. Thus $v_{n+1}$ cannot be smaller than $2 (n + 1 -1)$ because otherwise $v_n$ would be smaller than $2 (n - 1)$. The minimum can also be no larger than $2 (n + 1 -1)$, since this value is attained for simply placing the numbers in ascending order alongthe circle. Done.

Hello, I get a slightly different answer for the maximum. It must be a whole number.

I get,

maximum = trunc(x^2/2),

i.e., if n is even, maximum = n^2/2

if n is odd, maximum = n^2/2 - 1/2

I agree with your minimum.

Jao

cgjoa3 1 year ago

Hi Jao. The notation $\lfloor \cdot \rfloor$ I used is defined by:

$\lfloor x \rfloor := floor(x)$.

For $ x> 0$: $ floor(x) =trunc(x) $

Nelix 1 year ago
1 year ago

let start with number 1, minimum possible difference for next number is 1 so next number 2 and so on so minimum sum = n

for maximum::

let start with 1 and for max difference next number should be n, number next to n such that max. difference is there should be 2

so the series is 1,n,2,n-1,3,n-2,4,n-3....., and last n/2 or (n-1)/2 for odd and even n

so max = nn/2 or (nn-1)/2

1 year ago

Are these called purdue problems of week or nelix's math proofs of the week?! Jk wish more mathletes would participate !

1 year ago

As for minimality part : suppose the arrangement is a non - consecutive sequence .Then for sum p,q,r,s ยข N, p-q>1 , r-s>1 where p adjacent to q , r adjacent to s . wlog the last integer is not n ,so must be less then n-1 .wtf my phone is glitching out !;(

' half the problem for half the points ' ( lion's share had this been a putnam )Minimality of 2(n-1) Now we will show that $2n-2$ is minimal. To do so, remark that $1$ and $n$ must be on the circle. By the Triangle Inequality, the sum of the positive differences along the minor arc between $1$ and $n$ must be at least $n-1$ and similarly for the otherrh arc

Samurai 1 year ago

Post an answer:

To post an answer, please log in