2
$\begingroup$

Seventeen points have been picked in a plane, and each pair of points has been connected by a line segment of one of three colors: red, yellow, or green. Prove that there are three points which are the vertices of a monochrome triangle.

Monochrome triangle here means that all the sides of the triangle have the same color.

Source: The book, "A Moscow Math Circle" by Sergey Dorichenko.

I have seen the official answer given in the book. It is the same as the answer given by @KellyBundy below.

I want to see what other ways there are to solve this problem.

$\endgroup$
7
  • 1
    $\begingroup$ This is probably off-topic as a math problem. $\endgroup$ Jan 9, 2022 at 3:43
  • 1
    $\begingroup$ @Daniel It's actually Ramsey theory. The Clebsch graph shows that there is a colouring on 16 vertices without the listed property. $\endgroup$ Jan 9, 2022 at 7:17
  • $\begingroup$ @ParclyTaxel I am aware of this. The proof that the question asks for is not difficult. It is also not a puzzle. The question is therefore off-topic. $\endgroup$ Jan 9, 2022 at 7:26
  • $\begingroup$ As for many combinatorial problems, usually there could be multiple solutions indeed, but I'm currently doubting whether searching for other solutions fit for this site. I mean, I like combinatorics and would love to see multiple solutions, but just not sure whether this site is fit for that purpose. (also, this is standard question for Ramsey theorem, and the proof given in the current answer is the most straightforward proof using only PHP) $\endgroup$
    – justhalf
    Jan 9, 2022 at 9:12
  • $\begingroup$ @justhalf , understood. I am a teacher and want my students to look at a question from multiple angles. That is why I asked. Also, what does PHP mean here ? $\endgroup$ Jan 9, 2022 at 9:25

1 Answer 1

6
$\begingroup$

Pick a point. It has 16 edges of 3 colors, so at least 6 edges with the same color. Let's say red. Consider the 6 points at the other ends of those edges. If any two of them are connected with red, we have a red monochrome triangle. Otherwise we have 6 points only connected by green or yellow. Consider the subgraph of those 6 points and pick a point. It has 5 edges of 2 colors, so at least 3 edges with the same color. Let's say green. Consider the 3 points at the other ends of those edges. If any two of them are connected with green, we have a green monochrome triangle. Otherwise they're all connected with yellow and thus form a yellow monochrome triangle.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.