Multilingual hedge fund - Puzzle

Question

I'm having difficulty finding the solution for the following problem:

A hedge fund has 70 employees. For any two employees $X$ and $Y$ there is a language that $X$ speaks but $Y$ does not, and there is a language that $Y$ speaks but $X$ does not. At least how many different languages are spoken by the employees of this hedge fund?

My progress:

From the given hint, I know there are 70 unique combinations, such that, for any two sets, there is at least one element that is present in one set and not in the other.

From the formula of combination, I have:

$$x C y = 70.$$

I'm stuck at the above point, as there are two unknowns and one equation.

Answer 1

Without knowing the hint, I'm not entirely convinced that finding some minimal $x$ such that $\binom{x}{y} \geq 70$ for some $y$, will actually give you the smallest number of languages $x$. But after a bit of experimentation, this seems to be the right way to go. What you are missing is that for a given $x$, you want the $y$-value which gives you the maximum.

It is fairly well-known (from experience with the binomial distribution, anyway) that to maximize $\binom{x}{y}$ for $y$, pick $y = \lfloor x/2 \rfloor$. Also, the values $\binom{x}{y}$ will then grow roughly with $\sqrt{x!}$, so to get something as small as 70 it's easiest to just guess and check small numbers.

And indeed, $\binom{8}{4} = 70$.

Answer 2

I'm a little confused by the hint, but we can arrive at an answer by applying a theorem that's almost tailored to this problem! We want the 70 employees to define a Sperner system over a set of $n$ languages, which is known to require

$$\binom{n}{\lfloor n/2\rfloor} \geq 70$$

and therefore $n \geq 8$.

Answer 3

The individuals' language sets form an antichain. If the total number of languages spoken is $n$, Sperner's theorem states that the largest antichain (of subsets of the set of languages, with respect to the inclusion relation) has size $n \choose{\lfloor \frac{n}{2} \rfloor}$. The lower bound is then ${n \choose{\lfloor \frac{n}{2} \rfloor}} \geq 70$, or $n \geq 8$. The proofs of Sperner's theorem, which are beautiful but quite clever, show that for even $n$ the largest antichain is unique and is the middle-sized subsets. This makes rigorous Andrew Poelstra's answer and shows that the only solution with $8$ languages is to have every individual speaking $4$ of the tongues.

In essence the problem is asking you to intuit Sperner's theorem. The proof of the theorem is (probably) no simpler for $n=8$ than for general even $n$, which is to say that a job interview that asked this and expected a proof would be unsuitable for most positions held by math PhD's.

Answer 4

A logical way without prior knowledge of Sperner's Theorem

Using min no. of new languages L1...Ln "create" max no. of people P1...Pm. How do you "create" people? By assigning them a distinct subset of L1...Ln.

Realize that having people with unequal no. of languages is not helpful

Suppose we go with the strategy of unequal no. of languages The way to create max no of people would be to have nc1 people with 1 language, nc2 people with 2 language and so on. However that would fail. See how? Take this for example:

n=6
P1: L1 L2 L3 L4 L5
P2: L1 L2 L3 L4 L6
.
.
P6: L2 L3 L4 L5 L6

But after P6 we can only have 4 languages
P7: L1 L2 L3 L4

However, P7 does not have any language that P1 can't speak. So this strategy failed.

So if everyone has the same no. of languages, how do you create unique people?

Use combinatorics. Say everyone has k languages, then the max no. of unique people that can be formed out of n languages are nCk. Thus our objective boils down to

Find n & k such that nCk >= 70 for minimum n.

How to proceed after that if I don't know the Sperner's theorem?

No problems, just observe this

nCk, where n=4
4C0=1
4C1=4
4C2=6
4C3=4
4C4=1

The max value for nCk occurs in the middle (at k=floor(n/2)). Try for other numbers if not satisfied.

Final Step

Proceed from n=1 upwards till you get nCk>=70. You just have to check the middle value of eack n as a candidate for k.

1C1=1
2C1=2
3C1=3
4C2=6
5C2=10
6C3=20
7C3=35
8C4=70
There you have it at n=8

Thus, with this approach you can find the answer to any given n.