Each of $6$ points in space is connected to the other $5$ points by line segments.Each segment thus formed is colored greed or purple.Show that it is impossible to color all the segments without forming a triangle in which all three segments are the same color.

My efforts so far:

My initial guess was that this problem is somehow related to the pigeonhole principle,but I've not been able to use it in some usefull way.

I also think that this can be tackled using some combinatorial argument,however using brute force method i see that if we try to place colours such that no triangle of the same colour is formed this becomes impossible at the fifth point.

Finally can someone give some hint to put me on the right track for a proof ?

Thanks in advance.


Hint: Choose a point A. Point A is connected to five other points, so three of the connections are of the same color by the pigeonhole principle. Now consider the triangle they make.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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