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.

(In reply to Solution (possibly too informal) by nikki)

I'm not sure, but I think you're proof is too informal to be valid.  So I set out to find a counterexample.  Since the problem gives no doubt that it is true in this case, I will find a counterexample using different numbers.  If I am correct, your proof applies to the new numbers, and the counterexample proves it wrong.  If I am incorrect, your proof does not apply to the new numbers.

Let's say we are finding instead 50 groups each which includes one Spanish speaker, one French speaker, and one English speaker.

The counterexample:
There are 25 people who speak Spanish and English, 25 people who speak English and French, and 25 people who speak French and Spanish.  It is obviously impossible to find even one group with exactly 1 of each language.

This problem is at least slightly more complicated than it appears.

Posted by Tristan on 2004-11-10 18:46:06