The town of Friendville has an interesting property. Given any two people in the town, they either know each other or they don't. If they don't know each other, then they can be introduced to each other. One single introduction will work for both people. That is, "Tom this is Phil, Phil this is Tom" counts as one introduction.

The other interesting property that this town has, is that if any group of n people get together, the number of introductions that must be made in order that everyone in the group knows everyone else is at most n-1.

Problem: Prove that the town can be divided into two groups (A and B) such that everyone in group A knows each other, and everyone in group B knows each other.

the number of acquaintances within group A who know each other is : 

      A*(A-1)/2

and likewise within group B :

      B*(B-1)/2

The max. possible acquaintances within a group of (A+B), will be :

     (A+B)*(A+B-1)/2

As we are given that the max. missing acquaintances in a group of (A+B) will be (A+B)-1, therefore the min. of existing acquaintances  in this combined group will be :

      (A+B)*(A+B-1)/2 - ((A+B)-1) = (A+B-1)*(A+B-2)/2

 Now all we must show is that this min. number of existing acquaintances within (A+B) is larger or equal to the sum of acquaintances within A and within B , so that (A+B) can be broken into seperate groups A and B , that is, we have to show that :

    (A+B-1)*(A+B-2)/2 >= A*(A-1)/2 + B*(B+1)/2

    Opening the parentheses this leads to the requirement :

     A*B-A-B +1 >= 0  or :

    (A-1)*(B-1)>=0

   wich clearly holds for every positive A and B and (A+B) .

       Q.E.D

 

Posted by Dan Rosen on 2013-06-22 07:26:56