## Star Gazing

Posted on: March 29th, 2013 by
5

An astronomer observed 20 stars with his telescope. When he added up all the pairwise distances between the stars, the result was X. Suddenly a cloud obscured 10 of the stars. Prove that the sum of the pairwise distances between the 10 re- maining stars is less than 1/2 X.

Bonus: Can you improve the bound? What is the smallest real number r such that the new sum is always less than rX, regardless of the configuration of the stars?

#### 5 Responses to Star Gazing

I love puzzletweeter ðŸ˜€

Tell me if I'm wrong, but all I used is the triangle inequality repeatedly:
If one vertex is removed, then:
2(length of edges removed) >= X-(length of edges removed)
Thus on removing one vertex, pairwise distance sum becomes at most X(2/3). On further removal, we keep multiplying by a factor of 2/3. Thus on removing 10 vertices, the sum now becomes at most X*(2/3)^10, which is clearly much lesser than 1/2.

Why is it 2(length of edges removed)? Shouldn't it be (n-2)(length of edges removed) >= X-(length of edges removed), where there are n vertices initially?