3
$\begingroup$

Each of the vertices of a regular nonagon has been colored either red or blue. Prove that there exist two congruent monochromatic triangles.

My attempt:
We call a monochromatic triangle red (blue) if all of its vertices are red (blue). Because there are nine vertices colored in two colors, at least five must be of the same color. Without loss of generality, we say that this color is red. Hence there are at least ${5 \choose 2} = 10$ red triangles. Now, I have to prove that among these 10 triangles, there are two congruent triangles, which I can't imagine how am I supposed to prove. Please help.

N.B.: Solution containing application of bijection principle will be much appreciated. Thank you.

$\endgroup$
  • $\begingroup$ Can you count how many incongruent triangles can be formed from the vertices of a regular nonagon? Are there fewer than 10? $\endgroup$ – Greg Martin Jun 18 '14 at 23:29
1
$\begingroup$

Each triangle $\{v_1,v_2,v_3\}$ has associated to it a set of numbers $\{d_1,d_2,d_3\}$ where $d_1$ tells you how many vertices are between $v_1$ and $v_2$

in the clockwise direction. This set adds up $6$. two triangles are congruent if and only if they have the same set. So how many sets are there? This is the same as the number of partitions of $6$ into $3$ non-negative integers. You can count it by dividing into cases depending on how many distinct elements there are. and using the fact stars and bars tells us there are $\binom{8}{2}=28$ ordered ways to add it.

$1$ distinct element: 1 case $(2,2,2)$, also 1 ordered solution.

$2$ distinct elements: 3 cases $(0,0,6),(1,1,4),(3,3,0)$, 9 ordered solutions.

$3$ distinct elements: The remaining $18$ ordered solutions and therefore $3$ cases

So there are $7$ different shapes of triangle.

Using your result at least one color contains $5$ vertices, and therefore $10$ monochromatic triangles of that color. Since there are $10$ monochromatic triangles of that color and only $7$ shapes of triangle we must have at least two of those are of the same shape

$\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.