**Source:**Quantnet Forums

**Problem:**

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

The answer for 71 people should still be 8 but this method gives answer as 9.

DeleteIs this approach right?

70 people : Take one language. x people speak it and 70-x don't. Hence the total number of languages required = 1 + Max(total_languages(x),total_languages(70-x)). For least number of languages, x = 70 - x. Hence x = 35

and so on.... after that x= 18.... and then x = 9 ..... then 5... then 3... then 2.... then 1

This approach gives for 71 people total languages = 8

This comment has been removed by the author.

DeletePlease Ignore. I messed up the solution.

DeleteThis is based on Sperner's Theorem.

ReplyDeleteIn this case ans is 8.