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 :)

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.
