We consider dissections of regular $n$-gons into $n - 2$ triangles by $n - 3$ diagonals which do not intersect inside the $n$-gon. A bicoloured triangulation is such a dissection of an $n$-gon in which each triangle is coloured black or white and any two triangles which share an edge have different colours. We call a positive integer $n \ge 4$ triangulable if every regular $n$-gon has a bicoloured triangulation such that for each vertex $A$ of the $n$-gon the number of black triangles of which $A$ is a vertex is greater than the number of white triangles of which $A$ is a vertex. Find all triangulable numbers.
Problem
Source: Middle European Mathematical Olympiad I-2
Tags: geometry, combinatorics, memo
randomusername
25.09.2014 00:16
Take a successful triangulation.
The condition implies that at each vertex, we have one more black triangle than white.
The number of vertices of the black triangles minus the number of vertices of the whites (counting with multiplicity) is therefore exactly $n$. By definition, this number is divisible by $3$, $3|n$.
We can quickly construct a triangulation for $3|n$ by easy induction on $n$.
So the solution is exactly $3|n$, $n\ge 4$.
johnmichaelwu
03.10.2014 15:26
For a full solution of what @randomusername is saying.
Let $D$ equal the difference between the number of black and white triangles. Let's double-count this quantity.
Count the number of sides of black triangles, and subtract the number of sides of white triangles. By the condition, each diagonal is counted twice as the side of a white triangle and black triangle. Thus this difference is $\le$ the number of sides of the polygon. Since this triple-counts the difference between the number of black and white triangles, $D\le\frac{n}{3}$.
Now count the find the difference between the number of black and white vertices. By the condition, this is $\ge n$, since at each vertex there is a discrepancy of $\ge 1$. Since this triple-counts the number of black and white triangles, $D \ge \frac{n}{3}$
We conclude by the Squeeze Theorem that $D=\frac{n}{3}$. Since $D\in\mathbb{N}$, $3\mid n$. Let us now show that every multiple of three is in fact possible.
Let $n=3m$, and induct on $m$.For the easiness of induction, we add the additional claim that a $3m$-gon can be tiled in the requested manner with its entire perimeter consisting of only black sides. The base case $m=2$ consists of a hexagon with a white equilateral triangle in the middle, and black isosceles triangles along the sides. Now assuming that $m=k$ is possible with vertices $A_1A_2\cdots A_{3k}$, construct $3$ new vertices $A_{3k+1}A_{3k+2}A_{3k+3}$ between $A_{3k}$ and $A_1$. Then let $\triangle A_{3k}A_{3k+2}A_1$ be white, $\triangle A_{3k}A_{3k+1}A_{3k+2}$ and $\triangle A_{3k+2}A_{3k+3}A_1$ be black. Keep the rest of the polygon in the same state as it was before. It's clear that this polygon works.
We conclude that the polygons with this property are the multiples of $3$.
Niosha
30.03.2015 12:41
We could see that a bit different. Black triangle : $B$ White triangle: $W$ we can easily get each segment comes in one or two triangle. claim1 : if our segment is one if the sides,it comes in one triangle and that triangle is black consider that our segment is between two vertices $n$ & $m$ . now if you see from $n$ if the first triangle( which cotain our segment)be white then the sequence of the triangles that contain $n$ is like this: $W$, $B$, $W$,.... so the number of our $W$ is more than or equal to our $B$ which is a contradiction. claim2 : if our segment is one of the diagonals, it comes in two triangles and exactly one of them is black Because of our problem conditions! the number of black triangles : $N$ So from our claims : $3N = n-3$ => $3\mid n$ The rest of my solution is same as the others
rkm0959
30.08.2016 03:02
Calculate "number of black triangle - number of white triangle" in two ways. 1. By calculating "number of times this vertex was used as a part of a black triangle - same thing but white triangle" Using the condition that this value is $ \ge 1$ for each vertex. 2. By calculating "number of times this edge was used as a part of a black triangle - same thing but white triangle" Using the trivial observation that diagonals are once used as a part of black triangle and once used as a part of white triangle. Also, use the observation that each edge of the $n$-gon is used once. These two give us that our desired value at the beginning is $\frac{n}{3}$ by double counting. Therefore $3|n$. Construction is easy and inductable.