For every set S of at most n people, there is at least one person outside of S who is friends with everyone in S. Let $n$ be a positive integer. In a group of $2n + 1$ people, each pair is classified as friends or
strangers. For every set $S$ of at most $n$ people, there is at least one person outside of $S$ who is friends with everyone in $S$. Prove that at least one person is friends with everyone else.
 A: Take two disjoint sets of $n$ persons $A$ and $B$ such that the number of friendships between $A$ and $B$ is the minimum possible. Suppose that call the remaining dude $x$ and suppose that $x$ doesn't know everyone in $A$. Notice that if we swap the dude in $B$ that knows everyone in $A$ with $x$ we get even less friendships between $A$ and this new set. Hence we conclude $x$ knows everyone in $A$ and analogously $x$ knows everyone in $B$
A: The same is true for a group of $2n$ people. In general, given a (finite) set $V$ of people, if for every set $S\subseteq V$ with $|S|\le\frac12|V|$ there is a person in $V\setminus S$ who is friends with everyone in $S$, then somebody in $V$ is friends with everyone else.
It will be convenient to restate the proposition in terms of graph theory. Recall that a dominating set in a graph $G$ is a set $S$ of vertices such that every vertex not in $S$ is adjacent to a vertex in $S$; the domination number $\gamma(G)$ is the minimum number of vertices in a dominating set.
Let us consider the "stranger graph" $G=(V,E)$: the vertex set $V$ is the set of people, and two people are joined by an edge iff they are strangers. The condition "somebody not in $S$ is friends with everyone in $S$" means that $S$ is not a dominating set; and the statement "somebody is friends with everybody else" means that there is an isolated vertex. Hence the generalized version of your problem, for an odd or even number of people, is equivalent to the following simple fact about the domination number of a graph:
Theorem. If a graph $G=(V,E)$ has no isolated vertices, then $\gamma(G)\le\frac12|V|$.
Proof. Let $H$ be a spanning subgraph of $G$ which is minimal with the property of having no isolated vertices. In the graph $H$, each edge is incident with a leaf (vertex of degree one), otherwise we could remove it and still have no isolated vertices. Now it is clear that $H$ is an acyclic graph, i.e. a forest, every connected component is a tree. Moreover, it is easy to see that a tree, in which each edge is incident with a leaf, is a star; so $H$ is a forest of stars. By picking a central vertex from each of those stars, we get a set $S$ which is a dominating set for $H$ and therefore also for $G$; and $|S|\le\frac12|V|$ since each of those stars has at least two vertices.
