Problem #PRU-31363

Problems Methods Algebraic methods Partitions into pairs and groups; bijections Pigeonhole principle Pigeonhole principle (other) Proof by contradiction

Problem

a) In a group of 4 people, who speak different languages, any three of them can communicate with one another; perhaps by one translating for two others. Prove that it is always possible to split them into pairs so that the two members of every pair have a common language.

b) The same, but for a group of 100 people.

c) The same, but for a group of 102 people.