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.

  • 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

2

OK, the answer is $17$. The solution doesn't involve any case analysis, but it is far from elegant.

For an example with $17$ pairs of friends, see the comments to the question. I will only prove that the number of pairs of friends is always at least $17$.

We can describe the situation by an undirected graph $G=(V, E)$ with $|V|=12$ vertices. Choose an arbitrary vertex $a \in V$. Let $A$ be the set of all the vertices that are connected to $a$. Note that the diameter of $G$ is at most $2$, which means that every vertex $b$ from the set $V\setminus (A \cup \{a\})$ is connected to some vertex $c$ from $A$.

Now we will split $V\setminus(A\cup\{a\})$ into two subsets. Let $B$ be the set of all vertices from $V\setminus(A\cup\{a\})$ that don't have any neighbours in $V\setminus(A\cup\{a\})$, and let $C=V\setminus(A\cup B \cup\{a\})$.

For any two subsets $X$ and $Y$ of $V$, let us denote by $n(X, Y)$ the number of edges having one end in $X$ and the other in $Y$. Due to the construction of $a, A, B$ and $C$ we have: $ n(a, B) = n(a, C) = n(B, C) = n(B, B) = 0. $ Therefore, the total number of edges in the graph is $ |E| = n(a, A) + n(B, A) + n(C, A) + n(A, A) + n(C, C). $ Now we will make some estimates on the individual terms. It is clear that $n(a, A) = |A|$ and that $n(C, A) \geqslant |C|$.

To make an estimate on $n(B, A)$, let us consider any vertex $b \in B$. As we know, it has at least one neighbour $x$ in $A$. Also, $b$ and $x$ have a common neighbour $y$. $y$ cannot be $a$, because $b$ isn't connected to $a$. $y$ cannot belong to $B \cup C$ by definition of $B$. Therefore, $y \in A$. So, every vertex $b \in B$ has at least $2$ neighbours in $A$, and $n(B, A) \geqslant 2 |B|$.

For an estimate on $n(A, A)$, consider vertex $a$ and any $x \in A$. They have a common neighbour $y$. Since $y$ is connected to $a$, $y \in A$. So, every vertex in $A$ has a neighbour in $A$. One can easily see then that $n(A, A) \geqslant |A|/2$.

Finally, let's make an estimate on $n(C, C)$. By the construction of $C$, every vertex of $C$ has a neighbour in $C$, therefore $n(C, C) \geqslant |C|/2$.

Putting all the estimates together, we get $ |E| \geqslant |A| + 2|B| + |C| + \frac{1}{2}|A| + \frac{1}{2}|C| \geqslant \frac{3}{2}(|A| + |B| + |C|) = \frac{3}{2} \cdot 11 = 16\frac{1}{2}. $ And so we have it: $|E| \geqslant 17$.

  • 0
    Hm. Well, I guess a well-trained 14 year old could find a solution similar to this one. Kids can be extremely scary ) But if the other problems are easy, then it does look suspicious. Maybe we are all missing a short simple idea.2012-11-09