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 think this is similar to previously suggested proofs, as I skimmed through them, but it may go a bit farther.

First, make as many groups as possible with exactly one student speaking each language. As stated earlier, it's possible not all students may be able to be accommodated this way.

The remaining students must be such that no combination of them could form one of these groups. Also note that the same number of these remaining students must speak a particular language since you started with the same number of students per language and removed an equal number of each.

However, then it follows that the remaining students must speak two languages (and an equal number speak each pair of languages) -- thus simply form groups of 3 students with one student for each pair of languages to create a group with two of each language, and add the previous groups (with one of each language) to create the desired groups of 10 each.

The reason this follows is if there were at least one student who spoke each pair, then if the number of students who spoke one pair was smaller than the other two pairs, it would be impossible for there to be an equal number of students per pair.

If only two pairs of languages were represented among the remaining students, then all students would have to speak the language common to those pairs. (This would be impossible, since more students would speak the common language than the other two). If any student did not, then that student would speak one language, and could be combined with one of the pairs to form a group with one student who spoke each language, which was assumed to not exist.

Similarly, if one pair of languages existed, no one could speak the third language, as they could be combined to form a group, and thus fewer students would speak the third language than the other two.

If no pairs of languages existed, then either there is an equal number of students who speak only one language (which is assumed impossible) or there are no students left (in which case create the desired groups from the groups with one of each language).

Posted by Gamer on 2011-12-10 18:16:13