In a group of students, 50 speak English, 50 speak French and 50 speak Spanish. Some students speak more than one language. Prove it is possible to divide the students into 5 groups (not necessarily equal), so that in each group 10 speak English, 10 speak French and 10 speak Spanish.

I wish I could come up with an existence proof that isn't constructive, but so far I am blank. But I do have a construction that could probably be generalized, and I would appreciate some critical thoughts. Let’s create two types of small groups of people; I will call them 1-superspeaker and 2-superspeaker. Continue to iterate at a single step until the hypothesis no longer remains true. The intent is to slowly exhaust the main group while maintaining an equal number of speakers of each language. Thus, when all of one language speakers are assigned, the main group will be empty.

1) Each tri-linguist  is labeled a 1-superspeaker and removed from the main group. After this step, there are no remaining tri-linguists.

2) If there is a mono-linguist in the remaining group that only speaks English, then there must be a person that speaks Spanish and not English. Otherwise there is at least one more English speaker than Spanish speakers, namely, our mono-linguist English speaker we have selected. The same argument works for the existence of a person in the group that speaks French and not English. Regardless if the Spanish and French speakers are realized as two mono-linguists or one bi-linguist, place them with the pure English speaker, label the group as a 1-superspeaker, and remove them from the main group. After exhausting the English speaking mono-linguists, use a similar argument and process on the French and Spanish speaking mono-linguists. After exhausting this step, the remaining group will have no tri-linguists and no mono-linguists.

3) For each Spanish-French speaking bi-linguist, there must be one English-French bi-linguist and one English-Spanish bi-linguist. The argument is like balancing a chemistry equation; since the main group has the same number of speakers of each language, there must be one English speaker to balance the Spanish-French bi-linguist. This English speaker must be bi-lingual (by construction), so he also speaks, say, French. But now the balance is off again, and no Spanish-French or English-French bi-linguist can help the balance. Thus, there must be a English-Spanish linguist around also. Place these three as a 2-superspeaker and remove from the group. After exhausting this stage, we have exhausted the group of all speakers.

Now consider what we have, small groups of people that represent 1 or two triads of languages spoken. Fill the 5 sets with 2-superspeakers first, not placing more than five of these 2-superspeakers in any one set. Fill in the holes with the 1-superspeaker groups.
This seems like this could be generalized way past the specific numbers of 5*10=50 and perhaps the 3 languages.

Posted by owl on 2004-11-13 14:23:07