Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Is this an interview puzzle? –  zyx Jul 22 '13 at 1:25
add comment

3 Answers

up vote 3 down vote accepted

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$.

share|improve this answer
    
Thanks, Andrew! Can you provide link to any reference that gives an intuitive understanding of how picking y = floor(x/2) will maximize xCy? –  Chander Shivdasani Jul 22 '13 at 1:07
    
A simple observation is that $\binom{x}{y} = \binom{x}{x - y}$, so that the binomial coefficients are "symmetric" as you range over $y$. A less-simple observation is that the binomial coefficients describe the number of ways to get $y$ heads after flipping $x$ coins. Since $\lfloor x/2 \rfloor$ is the intuitively most likely outcome, you'd expect there to be more ways to get $\lfloor x/2\rfloor$ heads than any other number. –  Andrew Poelstra Jul 22 '13 at 1:12
add comment

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$.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.