Triangle $\Delta GRB$ is dissected into $25$ small triangles as shown. All vertices of these triangles are painted in three colors so that the following conditions are satisfied: Vertex $G$ is painted in green, vertex $R$ in red, and $B$ in blue; Each vertex on side $GR$ is either green or red, each vertex on $RB$ is either red or blue, and each vertex on $GB$ is either green or blue. The vertices inside the big triangle are arbitrarily colored.
Prove that, regardless of the way of coloring, at least one of the $25$ small triangles has vertices of three different colors.
one can prove that on each side of the big triangle,we have odd number of $2-colored$ segments...
now we will give the problem a graph as follow...
for each one of the $25$ triangles put a vertex in $G$ and also another vertex representing the outside of the big triangle name it $o$...
and also name the small triangles which adjacent to the outside $A$ and the rest of them $B$,now we will represent the edges of the graph:
for the $25$ small triangles,if the segment between two of them was $2-colored$ then put an edge between them otherwise no...
and for the triangles which are adjacent to the outside,if the segment which seperates it from the outside was $2-colored$ put an edge between it and the vertex from outside...
ok now we know that the number of edges between the vertex of $A$ and vertex $o$ is an odd number (its the sum of three odd numbers so its odd) and in the other hand we know that the sum of the degress of a graph is even,so the number of odd vertex must be even,so there exists an odd vertex in $B$,so the degree of this vertex must be $1$ or $3$,but it cant be $1$ (check it your self,its easy to see) so it must be $3$ so this triangle has $3$ $2-colored$ segments,so it has $3$ different colored vertices...
test20 wrote:
This problem is a very special case of the so-called Sperner lemma.
(Which is at the heart of modern proofs of Brouwer's fixed point theorem.)
which you can find in page $148$ of the booke: Martin Aigner-Gunter M.ziegler:Proofs from THE BOOK third edition Springer
BaBaK Ghalebi wrote:
test20 wrote:
This problem is a very special case of the so-called Sperner lemma.
(Which is at the heart of modern proofs of Brouwer's fixed point theorem.)
which you can find in page $148$ of the booke: Martin Aigner-Gunter M.ziegler:Proofs from THE BOOK third edition Springer
Yeah.
Or in Shashkin's book on fixed points.
Or in hundreds of other books that discuss Brouwer's fixed point theorem.
Or in West's book on graph theory.
BaBaK Ghalebi wrote:
and in the other hand we know that the sum of the degress of a graph is even,so the number of odd vertex must be even,so there exists an odd vertex in $ B$
Well, I think this is wrong. Even if there doesn't exist any odd vertex in $ B$, the sum of degrees is even anyway, just that there is an odd number of edges...
I think I have found a generalized solution. Someone please tell me how to attach an attachment. I clicked "Add an attachment" and put the msWord document. But when I try to see preview it says "The Extention docx is not allowed"
I am sorry for late reply. I overlooked your previous post. And I dont blame you... I cant open it now either .
Assume there is no small triangle of three colors.
Name each small triangle $ GR,RB,BG$ if it has only {Green and red},{Red and Blue},{Blue and Green} respectively.and name a all-green triangle $ GR$, a all-red triangle $ RB$ and a all-blue triangle $ BG$. Two adjacent triangles of different names must have their common side of their common color(It is understandable).
Now divide the big picture into some regions such that each region has triangles of same names. The boundaries of the regions must be monochromatic. And two boundaries can not intersect each other. Because three vertices of the graph have fixed color there is one boundary separating one fixed vertex(i.e. $ P,Z,C$ in the pic) from the others. It will intersect two of $ PC,CZ,ZP$. Say the boundary is red. Let $ P$ the Red Point. It will intersect $ PZ$ and $ PC$. Now cut away one side of the boundary where $ P$ is. Now Name Another point $ P$ on the boundary. It is a fixed Red point. We now have a similar picture where the same arguments can be applied. Again we reduce the picture and continue until we reach a small triangle whose vertices are of different colors.
Thanks, Akashnil, but now I have a question
Please clearly define your "boundary".
What do you mean by "Because three vertices of the graph have fixed color there is one boundary separating one fixed vertex(i.e. $ P,Z,C$ in the pic) from the others."
Jumbler wrote:
Please clearly define your "boundary".
I hope the picture is sufficient(If you can see it this time ). It suffices all conditions except That all the three sides of the big triangle have all the three colors. The segments joining two points of the boundary are given in bold. Note that all points on them are of the same color. And if you made a picture you couldn't avoid it because each small segment of the boundaries are owned by two small triangles of different names and as proved earlier their two common vertices would have same color, the triangles' common color.
If you still want a definition of a boundary:
Given two adjacent regions their boundary is the intersection of the points of the two regions.
[Definition of region: Collection of points such that you can travel between any two points of it through sides of small triangles of same names. And a region must be non-extendable.]
Jumbler wrote:
What do you mean by "Because three vertices of the graph have fixed color there is one boundary separating one fixed vertex(i.e. $ P,Z,C$ in the pic) from the others."
A single region can not contain all of $ P,Z,C$(a region contains points of only two colors). Thus there exists such a boundary
I think there is a little problem in the last part of the proof. We can not reduce the picture into a small triangle. But it can be like this-- We can not reduce the picture continuously. Thus our assumption that "there is no small triangle of three colors" was wrong.
P.S:
Please excuse me... I am not very good at defining and English isn't my mother tongue and i am only 14 years old.
Tell me if you can see the picture or not, understand the proof or not.
No worries, Akashnil. I really appreciate your effort. I'm trying to understand more now.
But, can you elaborate how you "reduce" the picture, because I don't understand this part. Maybe a picture will help
massnet wrote:
No worries, Akashnil. I really appreciate your effort. I'm trying to understand more now.
Thanks.
massnet wrote:
But, can you elaborate how you "reduce" the picture, because I don't understand this part. Maybe a picture will help
Now we have a boundary that separates one of $ P,Z,C$ from others. It will intersect two of $ PZ,ZC,CP$. Say the boundary is green. then it will intersect those two of $ PZ,ZC,CP$ where green is allowed. Say green is allowed in $ PZ,ZC$. Thus $ P$ is green and it is in one side of the boundary. Now cut away that portion of the picture(From Construction1-1 to Construction1-2). Then name a point on the boundary $ P$.
We will have another picture where same reasons hold good. But we cannot cut the picture infinitely many times.(Actually two boundaries will touch each at some point which is impossible).Thus we get contradiction. Actually I have assumed the picture quite large.
