Maths Olympiad Prep

Library / /152 of 196

Combinatorics Difficulty 5.8 AIME, harder Prove it Soviet Union

Problem:

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

Solution

Solution:

Let EFEF denote the number of students speaking English and French. Similarly define ESES, FSFS, EE, FF, SS, EFSEFS. Then ES+EF+E+EFS=50ES + EF + E + EFS = 50, EF+FS+F+EFS=50EF + FS + F + EFS = 50. Subtracting: ESF=FSEES - F = FS - E. Similarly, ESF=EFSES - F = EF - S.

Pair off members of FSFS with members of EE. Similarly, members of ESES with FF, and members of EFEF with SS. The resulting pairs have one person speaking each language. If {ES}={F}\{ES\} = \{F\}, then the only remaining students are those in EFSEFS, who speak all three languages. We thus have a collection of units (pairs or individuals) each containing one speaker of each language.

If {ES}<{F}\{ES\} < \{F\}, then after the pairing off we are left with equal numbers of members of EE, FF, and SS. These may be formed into triplets, with each triplet containing one speaker of each language. As before we also have the students in EFSEFS. Again, we have partitioned the student body into units with each unit containing one speaker of each language.

If {ES}>{F}\{ES\} > \{F\}, then after the pairing off, we are left with an equal number of members of ESES, FSFS and EFEF. These may be formed into triplets, with each triplet containing two speakers of each language. So, in this case we partition the student body into units with each unit containing either one speaker of each language, or two speakers of each language.

Finally, we may divide the units into 55 groups with 1010 speakers of each language in each group.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.