Friends Problem (Basic Combinatorics) Let $k$ and $n$ be fixed integers. In a group of $k$ people, any group of $n$ people all have a friend in common.


*

*If $k=2 n + 1$ prove that there exists a person who is friends with everyone else.

*If $k=2n+2$, give an example of a group of $k$ people satisfying the given condition, but with no person being friends with everyone else.
Thanks :)
 A: For the second part, divide the $k$ people into $k/2=n+1$ pairs and let the two people in each pair not be friends, while everybody is a friend with all those people they are not paired with. As any group of $n$ people involve at most $n$ of these pairs, the remaining pair are friends with everybody in the group. (Lesson: Taking complements, i.e., working with the graph of non-friends, can be useful sometimes.)
Thinking about how this example just barely works might give you some ideas for proving the first part.
A: Let's start with a small example for problem 2, $n=2, k=6$.  Number the people $1$ through $6$.  As Harald Hanche-Olsen says, let $1$ not be friends with $2$, $3$ not friends $4$, and $5$ not friends with $6$.  Because of the symmetry, there are only two kinds of sets of $n$ to see if they have a mutual friend:  $1$ and $2$, who have $3,4,5,6$ as mutual friends, and $1$ and $3$, who have $5$ and $6$ as mutual friends.
The general idea is that any set of $n$ people only have $n$ non-friends among them, leaving $2$ people who are friends with all of them.
For problem 1, the key insight is that at least one person has two non-friends.  Again take $n=2, k=5$.  $1$ is not friends with $2$, $3$ not friends with $4$, but $5$ has to be non-friends with somebody, say $1$.  Now the $n=2$ people $1,3$ don't have any friends in common.  You will have to work on generalizing this.  The idea is that if you take a group of $n$ people, you have $n+1$ non-friends if one of the $n$ is the person with two non-friends.  That is everybody ($n+(n+1)=k$) so the group has no mutual friend.
A: The first part of this is just an expansion of Harald Hanche-Olsen’s answer.
For the second part number the $2n+2$ people $P_1,\dots,P_{n+1},Q_1,\dots,Q_{n+1}$. Divide them into pairs: $\{P_1,Q_1\},\{P_2,Q_2\},\dots,\{P_{n+1},Q_{n+1}\}$. The two people in each pair are not friends; i.e., $P_k$ is not friends with $Q_k$ for $k=1,\dots,n+1$. However, every other possible pair of people in the group are friends. In particular, 


*

*$P_k$ is friends with $P_i$ whenever $1\le i,k\le n+1$ and $i\ne k$,  

*$Q_k$ is friends with $Q_i$ whenever $1\le i,k\le n+1$ and $i\ne k$, and  

*$P_k$ is friends with $Q_i$ whenever $1\le i,k\le n+1$ and $i\ne k$.


In short, two people in the group are friends if and only if they have different subscripts. Clearly no person in the group is friends with everyone else in the group. Suppose, though, that $\mathscr{A}$ is a group of $n$ of these people. The people in $\mathscr{A}$ have altogether at most $n$ different subscripts, so there is at least one subscript that isn’t used by anyone in $\mathscr{A}$; let $k$ be such a subscript. Then everyone in $\mathscr{A}$ has a different subscript from $P_k$ and is therefore friends with $P_k$ (and for that matter with $Q_k$).
I hope to get to the first part a bit later.
