Saturday, February 16, 2008

And a triangulated triangle

Now, you have a triangulated triangle, and all the vertices are colores as red, green and blue. The vertices of the big triangle are respectively red, green and blue, and the vertices of the triangulation that are between the red and green one are red or green, those between the green and blue one are green or blue, and those between the red and blue one are red or blue. Prove that at least one triangle in the triangulation has exactly one vertex for each color.

Update (09/03/2008): Solution posted! (show solution)


nico said...

please excuse me for my bad english language.
first of all a consideration.
the number of vertices in the triangulation have to be finished. as a counterexample consider the triangle in C of vertices the third roots of unity, say a, a^2, a^3. let s_1, s_2, s_3 be respectively the segments that connect a, a^2, a^3 to the origin. for every n strictly positive integer and for i = 1, 2, or 3, let x_i,n be the point of intersection of s_i and the circonference centered in the origin and of ray 1/n. for example x_1,1 = a, x_2,1 = a^2, x_3,1 = a^3. for all n let x_1,n be red, let x_2,n be green and let x_3,n be blue. for all n > 2 let x_1,n be connected to x_2,n, x_3,n, x_1,n-1, x_2,n-1 and x_3,n-1. for all n > 2 let x_2,n be connected to x_3,n, x_2,n-1 and x_3,n-1. for all n > 2 let x_3,n be connected to x_3,n-1. this triangulation satisfies the hypothesis but doesn't thesys.

nico said...

in the previous comment i meant finite, not finished. sorry.

nico said...

please excuse me for my bad english language.
i have a solution, if you want find it by yourself don't read more.
solution -i hope :)
for the first comment at this post i can suppose that the number of vertices in the triangulation is finite. let be r_0, g_0, b_0 the vertices of the greatest triangle respectively of colour red, green, blue. the proof proceeds by induction in the number of triangles in triangulation.
if there is only a triangle obviously the thesys is true.
now let suppose the thesys for all triangulation made of less than n triangles is true.
if there is a directly connected to g_0 green vertices, let g_1 be its name, then g_1 is different from r_0 and b_0 and it is possible to delete g_0 and put in its location g_1, mantaining arcs exiting from g_1 and so obtaining a new great triangle with satisfies hipothesys and triangulated by less than n triangles. so, by inductive hipothesys, there exists a little triangle whit a red vertex, a green one and a blue one. that triangle is as subtriangle -or its deformation- of the starting triangle.
now let suppose there are no directly connected to g_0 green vertices, so the vertices on g_0b_0 side have to be blue. let b_1 be its name. remark that possibly b_0 = b_1. there is only a directly linked to both g_0 and b_1 vertex. let x_2 be its name, where x = b if vertex color is blue, otherwise x = r. let x_k be defined. if there exists only a directly linked to both g_0 and x_k vertex and k is not 1 then x_k = r_k lies on the g_0r_0 side. otherwise -yet k different from 1- there exists only a directly linked to both g_0 and x_k vertex different from x_k-1. let x_k+1 be its name. because the number of vertices is finite for any directly linked to g_0 vertex x there exists a k strictly positive integer s. t. x = x_k. let A be the set of directly linked to g_0 vertices. let be < the equivalence relation on A so defined: x_i < x_j iff i < j. A is well ordered by <, so because a red element exists is well defined the <-minimum of the set of red element of A. let r_k its name. so g_0, b_k-1 and r_k satisfy the thesys.

nico said...

great! another one. no more geometry problems :)

Stregatto said...

Hi, i think that it is possible to make your proof work with a couple of small tweaks, just reasoning inductively on the triangulations that are homeomorphic to a disc, and since the solution that i had in my mind is different i find your idea quite interesting.
I remark that i already supposed the triangulation to be finite (should a complicated case such as an infinite triangulation be contemplated in a problem, i will make it explicit). However, just out of curiosity, it can be proved that the triangulation of a compact space must always be finite (if you think about it, in you infinte 'counterexample' the point 0 does not belong to any triangle) because a triangulation is usually defined as a homeomorphism (note, not just a continuous bijective map) from a simplicial complex to the space, and in a simplicial complex the set of all the simplices that have a vertex v as 'face' (ie the triangles, edges, tetrahedrons, etc such that their closure contains v, plus of course v itself) are an open neighborhood N_v of v. Each such N_v contains exacty one vertex of the triangulation (that is v), and if i cover the triangle with all such N_v for all the vertices of the triangulation i have an open covering that is minimal, in the sense that no smaller subcovering can be found. On the other side, the triangle is compact, and thus a finite subcovering can always be found. So, the vertices must be in a finite number.

nico said...

my solution needs a clarification. if you start from the green vertex, the other green vertex may lie on the opposite side -of the outer triangle. in that case my argument is wrong. in any case it is possible to chose -indifferently- another outer vertex. it cannot be directly linked to the opposite side, so the proof run naming red green, green blue, blue red, R* G*, G* B* and B* R*, for any *.