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.

Printable View

- February 24th 2008, 11:03 PMperashseven 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.

- February 25th 2008, 08:10 PMThePerfectHacker
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.