A company of people is composed of 2n+1 people and is such that for any subgroup of n people from that company, one person outside of the subgroup knows all members of the subgroup. Prove that there is one person who knows everybody in the company.

Lets prove the resutl for induction, starting for n = 0. If the company has 2n+1 = 1 person, then that person knows everyone on the company.

Lets suppose now that the result is true for n, and we want to prove it for n+1. In other words, the company is composed of 2 (n+1) + 1 = 2n+3 people, and each subgroup of n+1 people is known outside by someone.

Lets take 2 persons A and B so that they dont know each other. Such those persons should exist, otherwise, everyone would know everyone and the exercise ends there. Lets call L the compliment of {A, B}; note that #L = 2n+1. For each subset S of length n of L we make a set of length n+1 by adding A. Since A and B doesnt know each other, we have that there exist x in L, with x outside of S such that x knows every element of S.

The inductive hypothesis states that there exist p in L such that p knows everyone on L. Not only that, but also p knows A, because every x taken before knows A, so will p. If p also knew b, then the exercise ends there. If that is not the case we group p and B together. For the same argument as before, there exist y in {p, B}^c such that y knows every element of {p, B}^c and B. Since p knows every element of {p, B}^c, then y also knows p, so p knows every element of the group.