Solution

These types of problems are based on a branch of combinatorics called Graph Theory. A graph is a collection of points, called vertices and line segments connecting these points, called edges. A complete graph is a graph where every two points are connected.

Part 1.

We have 6 people. Suppose that there is a complete graph of six vertices where the vertices represent the 6 people. Suppose further that if two people know each other, then the edge connecting their corresponding vertices is red; if two people do not know each other, then the edge connecting their corresponding vertices is blue. What we have to prove is that there exists at least one triangle all of one color. Notice that there are 5 edges from each point A. Since there are 2 colors and 5 edges, there must be one such color such that at least 3 of the edges are colored with it. Without loss of generality, suppose that that color is red. So there are 3 points, call them B, C, and D, that are connected to A by a red edge. If any 2 of these 3 points are connected by a red edge, say B and C, we have the desired triangle ABC which is all red. If, conversely, none of the 3 points are connected by a red edge, that means that they are connected by blue edges, thus forming an all blue triangle BCD.

Part 2.

We have 17 people. Now we construct a complete graph of 17 vertices. If two people can communicate in English, the segment connecting their vertices is red, if they can communicate in French the segment is blue, if they can communicate in German the segment if green. (If a pair of people can communicate in more than one language, only one randomly chosen color is used). We have to prove that there is a triangle all of one color. There are 16 edges from each point A. There are 3 colors, so we can conclude that at least 6 of the edges are of one color, say green without loss of generality. If any 2 of the 6 points connected to A by green edges are themselves connected by a green edge, we have an all-green triangle. If not, that meants that they are all connected by blue or red edges. But by the result of part 1, if we have 6 points connected by blue and red edges, we will have an all-red or all-blue triangle.

The proof of Part 3 is left to the reader. It is very similar to the proofs of part 1 and part 2.

Go Back to Combinatorics Problems