Results 1 to 2 of 2

Math Help - seven people

  1. #1
    Member
    Joined
    Nov 2006
    Posts
    152

    seven people

    Each person in a group of seven people speaks at most two languages, while among every three of them there are at least two who can communicate. Prove that there are three people who speak a common language.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Consider seven people. Fix one of the people. Now create three groups where the other two are disjoint (from all other ones) and the third stays fixed. Thus, we have people 1,2 speak same language; 3,4 speak same language; 5,6 speak same language. If any those speak the same language the proof is complete. Assume that they are distinct, for definiteness suppose: 1,2 speak English; 3,4 speak French; 5,6 speak German. Now if 7 speaks either one of the three languages the proof is complete. Assume that 7 speaks two new languages (or one new language, it would not matter) say Russian and Spanish.

    Pick person 1 (English), 3 (French), 7 (Russian, Spanish). Between these three people a common language is spoken. There are two cases: (i) 1 and 3 speak a common language, say American (ii) either 1 or 3 speak Russian or Spanish.

    In case (i) the proof is almost complete. Now pick 3 (American, French), 5 (German), 7 (Russian, French). Now 5 needs to speak a common language with 7 or 3 thus he speaks either Russian or Spanish or French or American. If it is French or American proof is complete. Say then 5 speaks Russian. Go to 1,3,6 similar situation thus either Russian or Spranish or French or American. If French or English proof is complete. If Russian proof is complete because now 5 speaks Russian too, so say he speaks Spanish. But then repeating this argument with 2,3,7 we get by pigeonholing that 2 speaks Russian or Spanish (if he does not speak American). In any way we twist it, it works.

    In case (ii) the proof can be brought to case (i). We choose 1,3,7 and said 1 speaks Russian (say). Now choose 2,3,7 it can be like in case (i) in that case it use case (i) and proof complete otherwise 2 or 3 speak Russian of Spanish, if Russian proof complete, so say Spanish. But then again do it with 2,4,7 if it is like case (i) then proof complete otherwise it will be by case (ii) and by pigeonholing if we always get type (ii) occurences then there are three people with a common language.

    This can be made a lot nicer, sorry for this ugly demonstration.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. set of all people
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 16th 2011, 01:27 PM
  2. Replies: 1
    Last Post: February 14th 2011, 07:18 AM
  3. How many people can be fed?
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: August 29th 2010, 02:23 PM
  4. hey people , pls help
    Posted in the Algebra Forum
    Replies: 0
    Last Post: May 1st 2009, 03:13 AM
  5. Three People and CDs
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: September 28th 2008, 06:51 AM

Search Tags


/mathhelpforum @mathhelpforum