0
$\begingroup$

Take any set S of 10 points in the plane in which no three are colinear. Color each of the $\binom{10}{2}$ line segments between two of these points with one of red or blue. Prove that there is either a red triangle whose vertices are in S or a set of 4 points in S such that all line segments between these points are blue.

My attempt is to pick one of those 10 points and draw 9 lines that are incident to this point. Then color each line red or blue. By the pigeonhole principle, at least 5 lines have the same color. Supposed there are 5 red lines, then we can see there is either a blue or red triangle. The second part of the question I'm lost on.

$\endgroup$
  • $\begingroup$ do i just deduce that if its not a red line joining the other points then its a blue line and do this four times to get the second part? $\endgroup$ – pop May 18 at 5:17
1
$\begingroup$

Notice that you are proving $R(3,4) \leq 10$ btw

You started (your pigeonholing) a bit too weak; if you fix a point $A$ the pigeon-hole principle gives that there are either 4 points that are red connected to A or there 6 that are blue connected to $A$ (because of $x+y-1 = 9 $ means either ...)

Case # 1 there are 4 red connected to $A$ call them $B,C,D,E$ then either there is a red edge amongst them or not ... you know the rest

Case # 2 there are 6 blue connected to $A$ call them $B,C,D,E,F,G$ then either there is a ... you know the rest ... (hint either a blue or red triangle amongst the $B,C,D,E,F,G$) ... and just in case you don't, read this article about friends and strangers and check out this video

Main point, use the computation of R(3,3) to compute R(4,3)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ for both cases, there is a red triangle or 4 blue line segments correct? $\endgroup$ – pop May 18 at 6:26
  • $\begingroup$ Yea actually you get something much stronger; a blue square with blue diagonals i.e. 6 edges (4 vertices) all blue $\endgroup$ – Pedro Juan Soto May 18 at 6:41
0
$\begingroup$

Hint: Do you know the corresponding result that if you have six points there is either a red or blue triangle? Starting with one point is a good idea, but having just three the same color is not enough. If there are four red segments among the nine, what about the segments that join those points? If there are six blue segments among the nine, what about the segments that join those points?

| cite | improve this answer | |
$\endgroup$

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.