On two dimensional plane given 17 points, that which three of them are not on one line.

Each line between 2 points colored in one color, red, blue or green.

Prove:

In above structure there at least one chromatic triangle.

Good-Luck!

Printable View

- August 6th 2010, 01:02 PMAlso sprach ZarathustraTriangles and stuff...
On two dimensional plane given 17 points, that which three of them are not on one line.

Each line between 2 points colored in one color, red, blue or green.

Prove:

In above structure there at least one chromatic triangle.

Good-Luck! - August 8th 2010, 12:51 AMVlasev
Ok, start off by choosing any vertex v. It has to connect to the other 16 vertices in some way. By the pigeonhole principle, at least 6 of those connections go to one color, say red (without loss of generality). Call the connecting vertices v1,v2,v3,v4,v5 and v6. Without loss of generality, pick vertex v1. It must connect to the other 5 vertices. If there is the color red, there is a monochromatic triangle, so don't do that. We can color by only 2 colors, blue and green. Again, by the pigeonhole principle, at least 3 of those connections must be of one color, say blue. Without loss of generality, let these connections be to the vertices v2,v3 and v4. Now lets look at those 3 vertices. They connect to vertex v with color red, so if they have a connection in color red, we have a monochromatic triangle, so don't do that. They are connected to v1 with color blue and if there is a connection between v2,v3 and v4 in blue, then we have a triangle, so don't do that. We can only use one color for the connections - green. However, since these 3 connections form a triangle, we are forced to have a monochromatic triangle.

QED - August 8th 2010, 01:13 AMAlso sprach Zarathustra
One point to Vlasev.