multilingual

[radosr]

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?

 

[bigbadwolf]

Is it precisely one language that X speaks and Y does not or at least one?

 

[radosr]

Is it precisely one language that X speaks and Y does not or at least one?

at least one.

 

[pplstuff]

7

 

[koupparis]

Think of generating IDs for each person. Since each person must have at least one language the other doesn't know and vice versa, this amounts to generating 70 distinct IDs with 0s and 1s in each slot representing knowledge of a language or not. What is the smallest length of the ID? 2^n - 1 >= 70, subtracting 1 since ID= 0...0 should be excluded, n = 7.

 

[bigbadwolf]

Think of generating IDs for each person. Since each person must have at least one language the other doesn't know and vice versa, this amounts to generating 70 distinct IDs with 0s and 1s in each slot representing knowledge of a language or not. What is the smallest length of the ID? 2^n - 1 >= 70, subtracting 1 since ID= 0...0 should be excluded, n = 7.

I'm not sure it works since for example one person could be 1010101 and the second could be 1010100. There is one language that the first speaks but not the second but no language that the second speaks but not the first.

 

[koupparis]

I stand corrected, trying to think of a smart way to approach this.

 

[bigbadwolf]

I get 9 languages as the minimum.

 

[colincolinkn]

I get 9 languages as the minimum.

I guess 8 is the answer. At least there is a solution with 8 languages.

Every employee knows exactly 4 languages. Any two of them don't know the same 4 languages. Notice that there are 70 ways to select 4 languages out of 8 language, so this case works. (binom{8}{4} = 70)