9
$\begingroup$

I gave up, my approaches didn't work (induction, pigeon-hole, parity; though obviously there's a good chance I didn't use them cleverly):

In a group of 12 people, every pair of them has a common friend (in the same group). It is understood that friendship is a non-reflexive (a person is not a friend of herself), symmetric, not necessarily transitive relation (so this can be represented by a simple graph). What is the minimum number of pairs of friends among them?

(Source: Olimpiada de Mayo, 2012.)

So, how can this be solved (without considering lots of cases)?

Thank you.

  • 0
    non-transitive relation : A ~ B and B ~ C then A is not a friend of C Right ? What is the non-reflexive condition ?2012-11-09
  • 0
    @user37116 I edited it. Thank you.2012-11-09
  • 0
    I believe the answer is 21. Do you know the answer?2012-11-09
  • 0
    @Pambos I can do it with 17 and strongly suspect it can't be done with less.2012-11-09
  • 0
    I do not understand this problem : A and B share a fiend C Then B and C must share some friend D so that there exist a group {D, B, C} such that they are pairwise friend. So transfered !2012-11-09
  • 0
    Lower bound: everyone must have a friend (so they can have a common friend with somebody else); everyone must have two friends (so that they can have a common friend with someone who is their common friend with somebody else); so at least $\frac{2 \times 12}{2}=12$ friendship pairs. Upper bound: two people are friends with everyone including each other so $2\times 10+1=21$ friendship pairs. I would guess towards the top end.2012-11-09
  • 0
    @user37116. "NOT transitive" means that if A is a friend of B and B is a friend of C then *not necessarily* A is a friend of C. In the edit I wrote "not necessarily transitive" because of your comment, but "not transitive" should be enough.2012-11-09
  • 2
    @Henry Henry, Pambos: draw one in the center and the other 11 around. Make the one in the center friends with everybody else. Draw a polygon with the other 11, then remove as many sides of that polygon as you can. You get 17 pairs of friends.2012-11-09
  • 3
    Weltschmerz: Indeed, this is a [friendship graph](http://en.wikipedia.org/wiki/Friendship_graph) with 11 vertices and 15 friendships, plus 1 more vertex with 2 friendships of which one is to the friendliest vertex2012-11-09

1 Answers 1