# Maximize/Minimize It

Let $$x_1,x_2,\cdots,x_{19},x_{20}$$ be permutations of numbers from 1 to 20. Then what will be the maximum value of the summation $\large x_1x_2+x_2x_3+\cdots+x_{19}x_{20}+x_{20}x_1$ At which values of $$x_1,x_2,\cdots,x_{19},x_{20}$$ will that maximum occur? And when will minimum occur?

Note by Vilakshan Gupta
3 years, 7 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

I looked at this a little but I haven't done anything substantive. It seems like it should be possible to show that the minimum is obtained by alternating large and small numbers in a smart way.

E.g. for $n=4$ you get a minimum when you do something like $3142.$

For $n=6$ you do $351624.$

For $n=8$ you do $53718264.$

For $n=10$ you do $57391(10)2846.$ And so on.

Inductively, to get from one level to the next, it looks like you add two to the numbers larger than $n/2,$ and then on the outside you stick $n/2$ and $n/2+1$ in a smart way.

I don't have any kind of proof though, and I haven't thought about the maximum yet.

- 3 years, 7 months ago

For the maximum for $n = N$, going from $N$ down to $1$ while alternating from one side of the sequence to the other might be optimal. For $n = 4$ this would be $4213$, yielding a product-sum of $25$, (compared to your minimum of $21$), and for $n = 6$ it would be $642135$, yielding a product-sum of $82$, (compared to your minimum of $58$).

- 3 years, 7 months ago

Here's one idea I tried: for it to be a minimum (resp. maximum), the result has to be smaller (resp. bigger) than what you get after doing a transposition. For say $x_2,x_3,$ this ends up being the statement that $(x_1-x_4)(x_2-x_3) < 0$ (resp. $>0$). And so on for other pairs of adjacent indices. Your examples satisfy this criterion.

There is another condition you get if you transpose $x_2,x_4$ (say), and then you can look at a $3$-cycle too. Taken together, those give you pretty strong conditions on the permutation, but I don't know if they determine it uniquely.

- 3 years, 7 months ago

explain this

- 3 years, 7 months ago

again

- 3 years, 7 months ago

wc

- 3 years, 7 months ago

Please help me with this anyone. @Brian Charlesworth , @Chew-Seong Cheong , @Anirudh Sreekumar , @Sharky Kesa anyone?

- 3 years, 7 months ago