Fall 2015, problem 6
Comments
How did u get the second line ? Sum of(xi-xj)^2=n(n-1)-2sum xixj ? Did u just rearange ? Oh ok i think i get it now ! Sumxisquared and sumxjsquared are both n(n-1)/2 so added gives n(n-1) Right? And thats because any xi & xj are unit vectors ! Damn you are good lol if i was awarding points like the putnam for this problem u would get the ' full monte ' ..full 10 points ;)
Ok ive seen best solution on here ..great use of Cauchy Shwartz daesung ! I should now post an * original proof to match this one , but dont know how to write symbols on here as some kind of java script ? Or sumthing ;( But once i do figure out how to write in this language i will post it. It has to do with the centriod of the polyhedra formed by the points picked .dang wish i could write in the code uaed on here
We can proceed by induction and assume the result is true for some set of n points. Adding in an extra point means adding n extra distances to the sum, each of which is <= 2, i.e. adding a value <= 2n.
The distance between any two points on the unit sphere is <= 2 (as any two points lie on some unit circle).
For n = 1 the solution is thus obvious.
We can proceed by induction and assume the result is true for some set of n points. Adding in an extra point means adding n extra distances to the sum, each of which is <= 2, i.e. adding a value <= 2n.
Finally (n+1)^2 = n^2 + 2n + 1 >= n^2 + 2n so we're done.
(Sorry, haven't used latex for years. Will refresh myself, but please accept the plain text for this one).
EDIT
With regards to @Aaron_Hassan's point above, I assumed that we weren't counting distances twice. AND I failed to read the last part of the qn!
By the triangle inequality and taking into account Mr. Hassan's comment we have:
dist(Xi,Xj) = |Xi-Xj| <= |Xi| + |Xj|
Sum for all i less than j (there are n choose 2 such i and j combinations) and noting that |Xi| = |Xj| = 1 for i=1,2,...,n
Sum((i<j, dist(Xi,Xj) <= n(n-1)
And the result follows.
(Somehow, the less than sign (<) in my post doesn't seem to be displaying properly. It's being shown as a red "\ <".)
Is the inequality in the problem correct? If I have interpreted the notation correctly, it's asking to show that the sum of all $n^2$ distances between pairs of points is at most $n^2$, where we are including things like the distance between two same points (equal to $0$), and also counting things like $d(x_1,x_2)$ twice, as we include both $d(x_1,x_2)$ and $d(x_2,x_1)$, which are equal. This is because it has $i,j$ rather than $i \< j$ in the sum symbol.
If this is the case, I believe we can come up with counterexamples. For example, if we take $n=3$ and distribute the three points so that they form the vertices of an equilateral triangle inscribed in a great circle (radius 1 of course) of the sphere (https://en.wikipedia.org/wiki/Great_circle), then the distances between distinct vertices can be shown to be $\sqrt{3}$ using right-angled trigonometry. So the sum as I've interpreted would essentially involve summing the lengths of the three edges of this triangle and then mutliplying by 2 to account for the fact that we do things like include both $d(x_1,x_2)$ and $d(x_2,x_1)$. This gives the sum to be $2\times \left(3\sqrt{3} \right)=6\sqrt{3}=10.392\ldots > 9 = n^2$.
If the sum should have had $i \< j$, I think we can make the upper bound for the sum $n^2 - n$, but I haven't thought yet about whether this is the best general bound.
Hassan:
You are correct about the interpretation of the sum -- either i < j, or you have to divide the LHS by 2.
I did not have time to solve this. I have to admit that I violated the spirit of the POTW by looking up the answer. I won't spoil anyone else's fun by telling; however, since the problem statement is ambiguous at best (if not Just Plain Wrong), I will give a (small spoiler) hint: The actual tight inequality is the LHS above (with the i < j interpretation, i.e., the actual sum of all of the "n choose 2" Euclidean distances between the n points on the unit sphere) is <= n * (sqrt(n * (n-1)/2)). In case n = 3, 3 * sqrt(3) <= 3 * sqrt(3*2/2) = 3 * sqrt(3), so this checks out.
The distance between any two points on the unit sphere is less than or equal to 2. Since there are $n(n-1)\/2$ pairs between distinct points, there are that many nonzero terms on the left side. As a result, the left side is less than $2n(n-1)\/2 = n(n-1) = n^2-n\<n^2$. There is no case when the sum is $n^2$.
This was almost too simple. Am I missing something?
Let $x_{1},\cdots,x_{n}\in S$ and $N=\frac{n(n-1)}{2}$. By Cauchy-Schwartz inequality, we have $$ \sum_{i \\< j}d(x_{i},x_{j})=\sum_{i \\< j}|x_{i}-x_{j}|\leq \sqrt{N\sum_{i \\< j}|x_{i}-x_{j}|^{2}}. $$ Since $|x_{i}|=1$ for all $i$ and $$ \sum_{i \\< j}|x_{i}-x_{j}|^{2}=n(n-1)-2\sum_{i \\< j}x_{i}\cdot x_{j}=n^{2}-|\sum_{i=1}^{n}x_{i}|^{2}\leq n^{2}, $$ we obtain $\sum_{i \\< j}d(x_{i},x_{j})\leq \sqrt{Nn^{2}}=n\sqrt{\frac{n(n-1)}{2}}$ as mentioned above.