Question

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.

Answer 1

Explanation:

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.