Product of differences of circular permutation

122 Views Asked by At

Numbers $1,2,\ldots,n$ are arranged into a circle. What is the maximum product of the differences $|x_1-x_2|\times|x_2-x_3|\times\cdots\times|x_{n-1}-x_n|\times|x_n-x_1|$?

I think the maximum should occur when the numbers are arranged $n,1,n-1,2,n-2,3,\ldots$. The sum for this arrangement is $(n-1)(n-2)\cdots1\cdot\lfloor n/2\rfloor = (n-1)!\cdot\lfloor n/2\rfloor$.

This question was inspired by the question asking for the maximum sum. There, it is possible to prove optimality by noting that we have $2n$ terms ($n$ with $+$ and $n$ with $-$), and each number occurs twice.

Here, it is still true that we have $2n$ terms ($n$ with $+$ and $n$ with $-$), and each number occurs twice. But since we're taking the product instead of the sum, optimality is no longer clear.

1

There are 1 best solutions below

0
On BEST ANSWER

Your conjecture is false. Just generating some random permutations, for example, I find a permutation of 10, $2, 6, 1, 7, 3, 9, 5, 10, 4, 8$, for which the product of differences is $8294400$; compare $9! \times 5 = 1814400$ for yours. Note that all the differences in that permutation are 4, 5, or 6 (that is, near 10/2); I think the small factors in your product towards the end hurt you more than the large ones help.

As a result it makes sense to have as many factors near $n/2$ as possible, and I think something like $1, (n/2+1), 2, (n/2)+2, \cdots, n/2, n$ (for $n$ even) will do quite well - in this case you get a product of $(n/2)^{n/2} (n/2-1)^{n/2-1} (n-1)$.