# 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)$

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!

• If you use $x_1=5, x_2=4, x_3=2, x_4=1, x_5=3$, the sum for that case is $20 + 8 + 2 + 3 + 15 = 48$. Commented Apr 6, 2022 at 16:13
• The following permutations yield $48$: $$13542 \\ 21354 \\ 24531 \\ 31245 \\ 35421 \\ 42135 \\ 45312 \\ 53124 \\ 54213$$ Commented Apr 6, 2022 at 16:18
• To find $M$. Due to circular symmetry of expression WLOG $x_1=1$, then $S=x_2+x_2x_3+x_3x_4+x_4x_5+x_5$. Then search on all permutations of $(2,3,4,5)$ gives $M=48$ and there are two corresponding permutations $(2,4,5,3)$ and $(3,5,4,2)$. Circular shift multiplies number of such permutations by 5. Then $N=10$. Commented Apr 6, 2022 at 16:24
• @SlipEternal also 12453? Commented Apr 6, 2022 at 16:28
• Yes, that was in my list, I am not sure how I missed it. Commented Apr 6, 2022 at 16:30

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 57th Putnam (1996)).

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.