Source: Quantnet Forums
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?Update: (Dec 17, 2012)
Correct answer posted by Nikhil Jain (IT BHU Alumnus 2008), Paul Wong and Tuhin (IITB 4th year student) in comments.
Similar Problem:
A very similar but more difficult problem posted a couple of years back: http://pratikpoddarcse.blogspot.in/2009/12/number-of-locks-and-keys.html
2*ceil(log2(70)) ?
ReplyDelete8 languages.
ReplyDeleteMaximum number of unique combinations possible with 8 languages is 8c4 which is equal to 70. Thus if every employee knows 4 languages then 8 different languages will be sufficient to meet our case.
70..each employee speaks diff language...
ReplyDeletelet x be number of language, max combination when each one takes up x/2 number of language
ReplyDeletex C (x/2) >= 70
x = 8
The least number of languages that can be spoken are 8. Say the set of of languages be L = {A, B, C, .....}. Then for each of 70 employees, there should be a distinct combination for each of the 70 employees. We see that 8 distinct languages suffices because 8!/4!4! = 70, i.e, each of the 70 employees should choose a distinct 4 set from these 8 distinct languages
ReplyDelete7
ReplyDelete2^7=128 > 70
Either you know the language (think boolean 1) or you do not (think boolean 0). Number of unique combinations needed is more than 70.
(baki aap khud samjhdaar hain :P)
Vaibhav, The question asks for "at least" how many?
ReplyDeleteCorrect answer is 8. Thanks Nikhil, Paul and Tuhin for the correct answer.