Competition problem — Combinatorics

Library / /26 of 32

Combinatorics Difficulty 6.4 National Olympiad Prove it Romania

Consider $n$ persons, each of them speaking at most 3 languages. From any 3 persons there are at least two which speak a common language.

i) For $n \le 8$ , exhibit an example in which no language is spoken by more than two persons.

ii) For $n \ge 9$ , prove that there exists a language which is spoken by at least three persons.

Solution

i) Split the 8 persons in two groups of 4. Set any pair of persons in each group to speak a different language for a total of $6 + 6 = 12$ languages, each spoken by 2 persons, each person speaking 3 languages.

For $n \le 7$ , just remove $8-n$ persons.

ii) Assume by contrary that each language is spoken by at most two persons. Then each person $A$ can speak with at most three others, for otherwise, by pigeon-hole principle, there exists a language spoken by other two persons besides $A$ , a contradiction. Let $B, C, D$ the persons with whom $A$ can speak. Likewise, $E$ can speak with (at most) three others, namely $F, G, H$ . There is left at least another person, say $Z$ , and in the group $A, E, Z$ no language is spoken in common, a contradiction.

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.