Spring 2016, problem 9
Comments
' 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
If n is even, call the numbers n2..n the large numbers. Call the rest small. If n is odd call the numbers n+32..n the large numbers. Call n+12 the middle number.
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
Hi Jao. The notation $\lfloor \cdot \rfloor$ I used is defined by:
$\lfloor x \rfloor := floor(x)$.
For $ x> 0$: $ floor(x) =trunc(x) $
Are these called purdue problems of week or nelix's math proofs of the week?! Jk wish more mathletes would participate !
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 = n n/2 or (nn-1)/2
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 !;(