Meeting Problem

Part 1. In a meeting there are 6 people. Prove that there will always be a group of three people where each person knows all other people in the group, or a group of three people where none of them know each other. (Assume that if person A knows person B, then person B knows person A).

Part 2. In a meeting there are 17 people. Each person can speak English, German, or French, two of these languages, or all three. It is known that each pair can communicate with each other. Prove that there will always be a group of three people such that all three know a common language.

Part 3. In a meeting there are 66 people. Each person can speak English, German, French, or Spanish, or two or more of these languages. It is known that each pair can communicate with each other. Prove that there will always be a group of three people such that all three know a common language.

Solution

Go Back to Combinatorics Problems