Results 1 to 9 of 9

Math Help - How many different languages?

  1. #1
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    How many different languages?

    A company specializing in international trade has 70 employees. For any two employees A and B, there is a language that A speaks but B does not, and also a language that B speaks but A does not. At least how many different languages are spoken by the employees of this company?

    I think the answer is 70 (the case where each person speaks only one language - that nobody else speaks). Am I right?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

    Re: How many different languages?

    Quote Originally Posted by alexmahone View Post
    A company specializing in international trade has 70 employees. For any two employees A and B, there is a language that A speaks but B does not, and also a language that B speaks but A does not. At least how many different languages are spoken by the employees of this company?

    I think the answer is 70 (the case where each person speaks only one language - that nobody else speaks). Am I right?
    70 is a possible answer but not the least possible. 70 would be the minimum possible answer if one employee speaks only one language.

    EDIT: for example suppose the company only had 3 employees A,B and C. Then only 2 languages
    k and m would suffice. A speaks k and m both. B speaks only k and C speaks only n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: How many different languages?

    But then there does not exist a language that B or C speaks that A does not. In your example B speaks k and so does A which does not satisfy "and also a language that B speaks but A does not".
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

    Re: How many different languages?

    Quote Originally Posted by alexmahone View Post
    A company specializing in international trade has 70 employees. For any two employees A and B, there is a language that A speaks but B does not, and also a language that B speaks but A does not. At least how many different languages are spoken by the employees of this company?

    I think the answer is 70 (the case where each person speaks only one language - that nobody else speaks). Am I right?
    Now afgter some thought i think 7 languages will suffice. Let L is a seven element subset where each element of L represents a language. there are 2^7-1=127 proper subsets of a 7 element set. Choose any 70 subsets of L and assign each subset to an employee.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: How many different languages?

    Quote Originally Posted by alexmahone View Post
    A company specializing in international trade has 70 employees. For any two employees A and B, there is a language that A speaks but B does not, and also a language that B speaks but A does not. At least how many different languages are spoken by the employees of this company?

    I think the answer is 70 (the case where each person speaks only one language - that nobody else speaks). Am I right?
    The answer is 8.

    The requirement on A and B is equivalent to the statement that the sets of A's and B's languages are non-empty and neither is a subset of the other. Let there be 8 languages and assign each subset of size 4 to an employee. There are C(8,4) = 70 such subsets, and no subset of size 4 can be a subset of another subset of size 4.

    That at least 8 languages are required is a consequence of Sperner's Theorem:

    If A_1, A_2, \dots , A_m are subsets of N = \{1, 2, \dots , n\} such that A_i is not a subset of A_j if i \neq j, then m \leq \binom{n}{\lfloor n/2 \rfloor}.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: How many different languages?

    It can't be 8. Any repetition of a language at any point would allow you to find two employees A and B that both speak a common language. At least 70 must be spoken.

    Has the world gone mad or am I misunderstanding the question?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

    Re: How many different languages?

    Quote Originally Posted by terrorsquid View Post
    It can't be 8. Any repetition of a language at any point would allow you to find two employees A and B that both speak a common language. At least 70 must be spoken.

    Has the world gone mad or am I misunderstanding the question?
    suppose A speaks greek and latin and B speaks Latin and English. Then there exists a language (greek) which A speaks but B does not and there exists a language (English) which B speaks but A does not. Although there is a language(latin) which is shared by A and B still this doesn't violate the conditions of the question.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: How many different languages?

    Quote Originally Posted by abhishekkgp View Post
    suppose A speaks greek and latin and B speaks Latin and English. Then there exists a language (greek) which A speaks but B does not and there exists a language (English) which B speaks but A does not. Although there is a language(latin) which is shared by A and B still this doesn't violate the conditions of the question.
    Ah, ok. That makes more sense. I read it as A can't know a language that B knows etc. thanks. Although that is 3 languages for 2 people :S

    Your other example doesn't make sense though as B doesn't speak a language that A does not (and neither does C assuming m=n).

    So, an example of n people speaking less than n languages while satisfying the question would be:

    A(1,2), B(2,3), C(3,4), D(4,1), E(4,2), F(1,3)

    It seems you can't do it for less than 4 languages.
    Last edited by terrorsquid; August 22nd 2011 at 05:48 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

    Re: How many different languages?

    Quote Originally Posted by terrorsquid View Post
    Ah, ok. That makes more sense. I read it as A can't know a language that B knows etc. thanks. Although that is 3 languages for 2 people :S

    Your other example doesn't make sense though as B doesn't speak a language that A does not (and neither does C assuming m=n).

    So, an example of n people speaking less than n languages while satisfying the question would be:

    A(1,2), B(2,3), C(3,4), D(4,1), E(4,2), F(1,3)

    It seems you can't do it for less than 4 languages.
    yes i had realized my mistake. thanks anyway!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Automata Languages and DFA etc.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 20th 2011, 08:32 AM
  2. Languages and FSM.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 5th 2011, 01:09 PM
  3. context free languages
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 30th 2010, 06:11 PM
  4. countability of languages
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 21st 2010, 11:18 AM
  5. countable languages..please help!
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 17th 2010, 06:18 AM

Search Tags


/mathhelpforum @mathhelpforum