Log In

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?

via AMS puzzle corner


5 Responses to Star Gazing

  1. Aditya Mittal had this to say about that:

    I love puzzletweeter 😀

  2. Bharatram had this to say about that:

    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.

    • Gowtham had this to say about that:

      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?

      • Bharatram had this to say about that:

        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.


{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}