Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to solve the following problem :

In a group of $3n$ people each member knows exactly three languages from five given languages. Prove that it is always possible to partition the group into three groups of n people in such a way that in each group everybody knows at least one language from those five given . I tried to use the pigeonhole principle but it lead nowhere . A little hint would help a lot.

share|improve this question
    
I don't understand. Everyone knows three languages, then what is the problem? –  M.B. Nov 12 '13 at 17:33
    
They know three from five languages . Everyone doesn't know the same three languages –  user1978522 Nov 12 '13 at 17:35
    
@M.B.: But everybody in a group is supposed to share a language. –  Ross Millikan Nov 12 '13 at 17:35
    
@RossMillikan: ah right, fun problem. –  M.B. Nov 12 '13 at 21:25
    
Great problem. Using induction and separating a lot of cases will probably take it down, but that really is not the way you want to solve this. On the other hand, what is so special about 3 and 5? The problem has a Ramsey-flavor to it, but I cannot pin it down. In what context did it pop up? –  Leen Droogendijk Nov 13 '13 at 7:24

1 Answer 1

up vote 3 down vote accepted

It seems the following.

By induction we can prove more strong

Claim. It is always possible to partition the group into three groups $A, B,C$ of $n$ people in such a way that there exists three different languages $a$, $b$, and $c$ such that in the group $A$ everybody knows the language $a$, in the group $B$ everybody knows the language $b$, and in the group $C$ everybody knows the language $c$.

The base of the induction is trivial. Suppose that we already proved Claim for $n\ge 1$. Only the following cases are possible.

1) There exists a subgroup of three people which in common know all 5 languages an no two people of the subgroup know the same three languages. In this case by the inductive assumption we can divide the rest $3n$ people into three groups satisfying Claim for $n$. A short check shows that in this case we can always add exactly one of the people of the subgroup to each of the groups to satisfy Claim for $n+1$.

If Case 1 does not hold the one of the following cases hold

2) Each of the five given languages is known by some person of the group, but for each subgroup of three people which in common know all 5 languages there are two people of the subgroup who know the same three languages. In this case there is no two persons who in common know exactly 4 languages, because if we add to them the person who knows the fifth language then we obtain a subgroup satisfying the condition from Case 1. Suppose that a person knows languages 1, 2, 3. Then any other person can know one of the following set of languages: $\{1,2,3\}$, $\{1,4,5\}$, $\{2,4,5\}$, and $\{3,4,5\}$. Moreover, no two persons can know different sets of languages from the last three sets. So in this case we have a $k$ people who know the languages $\{1,2,3\}$ and $3n+3-k$ people who know the languages $\{a,4,5\}$ for some $a\in\{1,2,3\}$. For each value of $k$ it is easy to obtain the partition of the group satisfying Claim (if $k<n+1$ then the languages are $a$, 4, and 5; if $n+1\le k<2n+2$ then the languages are $a$, 4, and $b\in \{1,2,3\}\setminus\{a\}$; if $k\ge 2n+2$ then the languages are 1, 2, and 3).

If Cases 1 and 2 do not hold then we have Case 3, Case 4 or Case 5.

3) All persons of the group of $3n+3$ people know in common exactly 4 languages and there exists a subgroup of three people such that no two people of the subgroup know the same three languages. In this case by the inductive assumption we can divide the rest $3n$ into three groups satisfying Claim for $n$. A short check shows that in this case we can always add exactly one of the people of the subgroup to each of the groups to satisfy Claim.

4) All persons of the group of $3n+3$ people know in common exactly 4 languages and for any three people of the group two of them know the same three languages. In this case we obtain a partition satisfying Claim similarly to Case 2, but even simpler.

5) All persons of the group of $3n+3$ people know in common exactly 3 languages. In this case the required partition is trivial.

share|improve this answer
    
Good solution! Case 2 can be simplified if we notice that if at least two sets of persons who know languages $\{\,1,4,5\,\}$, $\{\,2,4,5\,\}$ and $\{\,3,4,5\,\}$ are non-empty then there are two persons who know $4$ languages in common. So WLOG there are only persons who know languages $\{\,1,2,3\,\}$ and $\{\,1,4,5\,\}$ and the claim becomes almost trivial. –  Smylic Nov 28 '13 at 9:13
    
@Smylic I did this simplificaltion in my solution, but to avoid comments I denoted this at most one non-empty set as corresponding to the set $\{a,4,5\}$ of languages. –  Alex Ravsky Nov 28 '13 at 9:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.