Permutation of points $P_i\in X$ such that $\sum^n_{j=1}|P_{\sigma(j+1)}-P_{\sigma(j)}|^2\leq 8$

Solution 1:

Let us prove that for arbitrary 3 points placed on a semicircle of unit radius, the sum $S$ of squares of their distances is less then or equal to 8.

Case 1: all three points on the diameter

It's easy to show that 3 arbitrary points shown on the left have smaller $S$ compared to the special case shown on the right ($AB<AB'$, $AC<AC'$, $BC<B'C'$

For the three points on the right:

$$S=x^2+(2-x)^2+2^2=x^2+4-4x+x^2+4=8-2x(2-x)$$

Obviously $x\le2$ so $S\le8$.

Case 2: Two points on the diameter, one point above on the circle.

Arbitrary case is shown on the left. For every such case it is possible to find a similar case, with one point on the diameter moved to the end of it, that has bigger $S$. For example, if ve move point $A$ to the left end of the diameter $BA'>BA$, $CA'>CA$. Now look at the picture on the right and triangles $A'BC$ and $A'BC'$. We want to prove that $S(A'BC)<S(A'BC'):$

$$S(A'BC)=c^2+a'^2+(2-x)^2=c^2+(a^2+x^2-2ax\cos\alpha)+4-4x+x^2=$$

$$S(A'BC)=c^2+a^2+4+2x^2-2ax\cos\alpha-4x=S(A'BC')-2x(2-x)-2ax\cos\alpha\le S(A'BC')$$

Note that $S(A'BC')=8$.

Case 3: Two points on circumference, one point on the diameter

For the triangle shown on the left, it is always possible to move one point to the end of the diameter and create a triangle that has a bigger $S$. For example, if you move point $A$ of triangle $ABC$ to point $A'$: $BA'>BA$, $CA'>CA$. So $S(ABC)\lt S(A'BC)$ and according to case (2), $S(A'BC)\le8$

Case 4: All three points on circumference

This case is trivial. Such triangle has smaller $S$ compared with triangle $A'BC'$ and according to case (2) $S(A'BC')=8$.

Solution 2:

I am not great with formal proofs, but I can explain to you how I would solve both questions in an intuitive way.

a) From the definition of X, you can visualize the semi-circle (the top half of the unit-circle). We must prove that there exists a formation such that all points $P_i$ connected to each other, their euclidean distances squared (summed up) remain smaller or equal to 8.

If you don't think about the squared part, but simply, such that each points on this semi-circle is connected to the next point. How can we order these points such that the length of the total amount of line drawn between these points is minimal? Clearly, ordering the points such that connecting them criss-cross from left to right and up and down, the amount of line drawn to connect them will be a lot. However, if you place them in order such that the points follow the semi-circle, the length will be 2 (from [-1,0] to [1,0]) + pi (half of the circle).

In the case of the sum which squares the distances between each point, you have to prove that for any set of points this total must always be smaller or equal than 8. We already found previously that without squaring, following the circle, this value can be 2+pi. If we square this same solution (in which the distance between each point is <1) the squared version will be even smaller. The only way to make it larger is by only including points which are more than 1 apart, since squaring would increase this total value. Maximizing this value requires you to travel the longest distance, which squared would lead to the highest value. Travel from [-1,0] to [1,0] = 2 (squaring makes this 4). Then moving back to the original point adds another 4, equaling 8. Any other points along the semi-circle will always bring you to a value < 8.

b) Agreed with your solution. The only answers I can come up with are {[-1,0];[0,1] or any other point along the semi-circle;[1,0]} and {[-1,0];[1,0]} in which $S_n$=8 in both occasions.