Friday, September 26, 2008

Challenge problem - From a classic Steven Krantz book -

I have simply been unable to crack this one, particularly the general version of this problem... any hints ?
You have six points on a piece of paper. Every point will be joined to every other point by either by a red line segment or by a blue line segment. You can colour any line in anyway you choose. Show that there will have to be either be a triangle that is all blue or a triangle that is all red.
Formulate a generalization of the last problem. Suppose that you have k colors. How many points are required to guarantee that the process of joining all possible pairs of points with line segment segments of one of these colors will guarantee that there is a triangle of just one color?

1 comment:

Vivek Athalye said...

i don't know if i understood the problem statement clearly. anyway, i'll let u know my thoughts...

i guess even if u have 5 points and 2 colors, then there will be atleast 1 triangle that has all the 3 lines of same color. correct me if i'm wrong.

the number of lines that will be drawn from each point will N-1, where N is the number of points. and the total number lines in the figure will always be (N*(N-1))/2.

now these equations coupled with 3 (sides of triangle) should give u the generalization that u r looking for... hopefully :D