0
$\begingroup$

In the plane for $7$ points distinguish no three points in line. The straight segment connecting any two points is colored blue or red. Prove that there are at least $3$ triangles with $3$ edges of same color.

I think there is $\binom 76$ set of $6$ points. Each of these sets contains a blue or red triangle so there are $7$ blue or red triangles, but there may be overlap

$\endgroup$
  • $\begingroup$ What do you mean about this problem Henning Makholm $\endgroup$ – J.doe May 19 '18 at 15:12
0
$\begingroup$

Call the first six points $A_1;A_2;A_3;A_4;A_5;A_6$ ($A_7$ will be used later).

We consider the segments $A_1A_2;A_1A_3;A_1A_4;A_1A_5;A_1A_6$. There are $5$ segments, using the Dirichlet process we can prove that at least $3$ of these $6$ segments share the same color.

Assume that the segments $A_1A_i;A_1A_j;A_1A_k$ has the same color and $\Delta{A_iA_jA_k}$ has three segments $A_iA_j;A_jA_k;A_kA_i$ $(i,j,k\in\mathbb{Z};1< i,j,k\le 6)$.

  • If $A_1A_i;A_1A_j;A_1A_k;A_iA_j$ are segments with the same color then $\Delta{A_1A_iA_j}$ has three segments with the same color.

  • If $A_1A_i;A_1A_j;A_1A_k;A_jA_k$ are segments with the same color then $\Delta{A_1A_jA_k}$ has three segments with the same color.

  • If $A_1A_i;A_1A_j;A_1A_k;A_kA_i$ are segments with the same color then $\Delta{A_1A_kA_i}$ has three segments with the same color.

  • If neither of the segments $A_iA_j;A_jA_k;A_kA_i$ have the same color as the segments $A_1A_i;A_1A_j;A_1A_k$ then the segments $A_iA_j;A_jA_k;A_kA_i$ $(\Delta{A_iA_jA_k})$ must be the same color, since there are only two colors.

We have proven that in any six points, there is at least one same-color triangle with $3$ of the $6$ points. Prove similarly for all other sets of six points:

  • $A_1;A_2;A_3;A_4;A_5;A_6$
  • $A_1;A_2;A_3;A_4;A_5;A_7$

  • $A_1;A_2;A_3;A_4;A_6;A_7$

  • $A_1;A_2;A_3;A_5;A_6;A_7$

  • $A_1;A_2;A_4;A_5;A_6;A_7$

  • $A_1;A_3;A_4;A_5;A_6;A_7$

  • $A_2;A_3;A_4;A_5;A_6;A_7$

For each of the sets of six points above, there is always at least one way to choose three points so that the triangle formed from $3$ points has three sides with the same color.

Without loss of generalization, assume that $\Delta{A_4A_5A_6}$ is a same-color triangle. Then the 5th, 6th and 7th bullets have already satisfied the conclusions above, but not for 2nd, 3rd and 4th bullets.

In order to prove that there exists at least $3$ same-color triangles overall, we need to prove that from the 2nd, 3rd and 4th bullets there are at least two different sets (in total) of three points, each of them comes from either 2nd, 3rd and 4th bullets. We should note that if we can find any set of three points other than $A_1;A_2;A_3$ that forms a same-color triangle from any of the three bullets, 2nd, 3rd, 4th, there will always be a different set in one of the two other bullets (I am sorry but I do not know how to clearly express this to make it easy to understand, although I know what I am doing).

By contradiction, from the 2nd, 3rd and 4th bullets we only need to prove that $\Delta{A_1A_2A_3}$ and $\Delta{A_4A_5A_6}$ cannot be the only two same-color triangles overall.

Lemma: Given $7$ points $A_1;A_2;A_3;A_4;A_5;A_6;A_7$, the straight segment connecting any two points is colored blue or red. Prove that it is not possible that exactly $\Delta{A_1A_2A_3}$ and $\Delta{A_4A_5A_6}$ are the only triangles that have all three sides same color.

$\endgroup$
  • $\begingroup$ Prove that there are at least 3 triangles with 3 edges of same color. $\endgroup$ – J.doe May 19 '18 at 14:25
  • $\begingroup$ I have just realised it too, I am now editing it, sorry. $\endgroup$ – Trần Thúc Minh Trí May 19 '18 at 14:26
  • $\begingroup$ There are not enough 3 triangles of the same color $\endgroup$ – J.doe May 19 '18 at 14:27

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.