[r-t] Little Bell Music (max possible "interval score")

[Alexander Holroyd]

Robert Johnson has provided the following answer to Ben Willetts'
question.

---------- Forwarded message ----------
<snip>

The answer is  as follows (at least for even n -- can't be
<snip>
to work out
the details for odd n).

Let;'s do the 'cyclic' version first (ie maximise |f(1)-f(n)|+ \sum_{i=2}^n |
f(i)-f(i-1)| )

For each adjacent pair of bells i,j with i<j form the set {i,i+1,i+2,....j-1}.
Let M be the multiset formed by taking the union of these. The sum we want to
maximise is equal to |M|.

How many times can i appear in M?
At most 2i, since there can be at most 2i pairs of adjacent bells one of which
is at most i.
Also, at most 2(n-i) since there can be at most 2i pairs of adjacent bells one
of which is greater than i.

So summing the max number of appearences of each of 1,2,...n-1 in M we get
|M|\leq (2+4+...+n-2)+(n+n-2+...+2)=n^2/2.

So for the cylclic version the sum is at most this and this is attained for
any permutation which alternates small  (ie 1,2,....,n/2) and large (ie
n/2+1,---n) bells.

For the non-cyclic version note that in going from viewing a perm cyclically
to viewing it non-cyclically we lose at least 1 from the sum. And if we
choose to split the cycle between n/2 and n/2+1 then we lose exactly 1.

So the answer is
\sum_{i=2}^n |f(i)-f(i-1)| \leq \frac{n^2}{2}-1
With equality iff f(1)=n/2 or n/2+1, f(n)=n/2+1 or n/2, and the permutation
alternates between elements of {1,2,...,n/2} and {n/2+1,...,n}.

Hope that makes sense.

R

> -----Original Message-----
> From:	Alexander Holroyd [mailto:holroyd at math.ubc.ca]

<snip>

> maximise \sum_{i=2}^n |f(i)-f(i-1)| where f is a permutation of 1...n
>
> [r-t] Little Bell Music
> Ben Willetts ben at benjw.org.uk
> Wed Sep 29 13:39:10 BST 2004

<snip>
>
> > I proposed that a good way to measure the
> > "musicality" of a row was to take the mean of the intervals
> > between adjacent blows.

<snip>
>
> (As an aside, what's the highest mean interval score a row can have?  Does
> Tittums always score the highest possible mean?)
>
> Ben