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?

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?

You are right. Bad counting on my part, but can be fixed as you said.

Removing one vertex from 20 makes the sum go down to at most X*(18/19), so removing 10 vertices makes it X*(18/19)(17/18)...(9/10).

This is X*(9/19), which is less than X/2.

So what about the smallest r?