Maximize $x_1x_2+x_2x_3+\cdots +x_5x_1$ where $x_1, x_2, \dots, x_5$ is a permutation of $(1,2,3,4,5)$

Question

Let $M$ be the maximum possible value of $x_1x_2+x_2x_3+\cdots +x_5x_1$ where $x_1, x_2, \dots, x_5$ is a permutation of $(1,2,3,4,5)$ and let $N$ be the number of permutations for which this maximum is attained. Evaluate $M+N$.

---

First, I tried testing some permutations, and see which one gives the largest sum. I think that $45$ is the largest sum possible, and that is when $x_1=1,x_2=2,x_3=3,x_4=4, x_5=5$, but I'm having trouble to prove this, and I'm also not quite sure how many of those permutations yields a sum of $45$.

I would appreciate any help!

Answer 1

For our purposes, a bracelet of length $k$ (with distinct beads) is an equivalence class of $k$-permutations $[s_1s_2\cdots s_k]$, where two permutations are considered equivalent if they are related by reversal or cyclic shift; for $k\geq 3$, there are $2k$ permutations in each class, so there are $\tfrac{1}{2}(k-1)!$ distinct bracelets of length $k$, and the present situation is $k=5$. A maximizing bracelet is one that maximizes the objective function

$$s_1s_2 + \ldots + s_{k-1}s_k + s_k s_1\text{.}$$

Call this maximized value $a_k$. Then by induction, one can show that, for each $k\geq 3$,

• there is a unique maximizing bracelet,
• $k$ and $k-1$ are adjacent in the maximizing bracelet, and
• $a_k = 2\,_kC_3 + 3 \,_kC_2 - \,_kC_1 + 3$.

In the base case, these claims hold because there's only one bracelet and $a_3 = 1\cdot 2 + 2\cdot 3 + 3\cdot 1 = 11$.

So let's assume the three claims hold at a given $k$. Every bracelet of length $k+1$ is found by inserting the "bead" $(k+1)$ between two adjacent beads $s_is_j$ in some unique bracelet $[s_1s_2\cdots s_k]$. The increase in the objective function is $$(k+1)(s_i + s_j) - s_is_j = (k+1)^2 -(k+1 - s_i)(k+1 - s_j)\text{.}$$

This increase will be maximized if $\{s_i,s_j\} = \{k,k-1\}$, in which case the increase will be $2\,_kC_2 + 3\,_kC_1 - 1$. Inserting the new bead there on the unique maximizing bracelet of length $k$, we get a bracelet for which the objective function takes the value $a_k + 2\,_kC_2 + 3\,_kC_1 - 1$. Now,

• inserting the new bead anywhere else on the maximizing bracelet produces a smaller objective function value and
• inserting the bead on any other bracelet of length $k$, we started with an objective function value less than $a_k$, so we must end up with an objective function value smaller than $a_k + 2\,_kC_2 + 3\,_kC_1 - 1$.

Consequently, there is a unique maximizing bracelet of length $k+1$, $(k+1)$ and $k$ are adjacent, and $$a_{k+1} = a_k + 2\,_kC_2 + 3\,_kC_1 - 1 = 2\,_kC_3 + 3 \,_kC_2 - \,_kC_1 + 3 + 2\,_kC_2 + 3\,_kC_1 - 1 =2\,_{k+1}C_3 + 3 \,_{k+1}C_2 - \,_{k+1}C_1 + 3\text{.}$$

Finally, the value you want is

$$\left. 2k + a_k\right\rvert_{k=5} = 10 + 48 =\boxed{58}\text{.}$$

See OEIS A110610 and references therein (in particular, the essence of this problem was on the 57^th Putnam (1996)).

Answer 2

The constraint requires (in effect) a (single) $5$ loop. That is, you can not have a $3$ loop of 5-4-3-5, combined with the $2$ loop of 2-1-2.

Initially, I also thought that the maximum is achieved by coupling 5-4 and (then) 4-3, which leads to 5-4-3-2-1 : $45$.

In searching for a maximum, the only alternative that I would consider is the loop of 4-5-3-1-2 : $48$.

Now, let's temporarily assume two things:

• $48$ is indeed the maximum.
• It can only be achieved by coupling $5$ with both $3$ and $4$.

Then, the issue is: how many distinct permutations will lead to the 4-5-3-1-2 loop. I say there are $10$ such permutations, because $x_1$ can be assigned to any of $4,5,3,1$ or $2$. Then, once $x_1$ is assigned (for example, $x_1 = 4$), then the loop must go in one of two directions. That is, if $x_1 = 4$, then the possible loops are 4-5-3-1-2 and 4-2-1-3-5.

So, assuming that $48$ is the max, and is only achievable with $5$ coupled with both $3$ and $4$, the answer would be

$$M = 48, N = 10. \tag1 $$

You can kill $2$ birds with one stone, by questioning which of the $2$ numbers in $\{1,2,3,4\}$ should be coupled with the $5$. Here, as shown: 3-5-4 is superior to 1-5-4-3. The 4-5-3 coupling (by itself) creates a partial sum of $35$ while the 5-4-3 coupling creates a partial sum of $32$.

Experimenting, I can't find any way of achieving $48$ (or higher) by anything other than 3-5-4-2-1 (in some permutation). Assuming that I haven't overlooked anything, inelegant trial-and-error indicates that the answer given in (1) above is accurate.