For all odd number $ n$ that $ n>1$ First of all since there are $ C^n_3$ ways to choose 3 among $ n$ colors, and $ C^n_3$ ways to choose 3 vertices to form a triangle, so if the question's condition is fulfilled, all the triangles should have different color combination among each other. (a 1-1 correspondence) (From now on i shall include "sides" in "diagonals" for convenience.) As each color combination is used in exactly one triangle, for each color, there should be $ C^{n-1}_2$ triangle which has one side in this color. Now there are $ C^n_2$ diagonals in the polygon and for each diagonal, there are $ n-2$ triangles with this diagonal as side. If $ n$ is even, $ (C^n_2)/n$ is not an integer, so there exist at least one color where the number of diagonals with this color is less than $ (C^n_2)/n$, i.e. there are less than $ (C^n_2) \times (n-2)/n = C^{n-1}_2$ triangles with a side in this color, contradiction. So $ n$ is odd. Now gives a construction method for all $ n$ is odd. As the orientation of the vertices doesn't really matters, we assume that the polygon is a regular $ n$ polygon. First color the $ n$ sides of the polygon in the $ n$ distinct colors. Then for each side, color those diagonals that are parallel to this side into the same color. In this way, for each color, there are $ (C^n_2)/n$ diagonals colored in this color, notice that each of these diagonals are of different length...(i) Besides, for any two triangles with all vertices in $ P$, I shall prove that they should have different color combination. Suppose the contrary, i.e. they have exactly the same three colors as their sides. For two of the 3 colors, the corresponding sides in the two triangles should have the same included angle since two sides are of the same color iff they are parallel. However, notice that the third side of each triangle, i.e. the side opposite to that included angle, should have the same length. (Since a regular n-gon is circumscribed by a circle, in a circle, same angle correspond to same side) But this is obviously impossible since they have the same color, contradict to (i). This completes the proof.

For odd $ n$, consider the following coloring: label the vertices with $ 1, \ldots, n$ and color segment $ ij$ by the $ (i + j \bmod n)^{\mathrm{th}}$ color.

Easy problem! at first step we will prove that the number of vertexes of $G$(which is $n$) can not be even. suppose the number of vertexes of $G$ is even. the number of edges which colored by color $i$ is less than $n/2$(which is a contradiction) since if its equal $n/2$ , we have $n/2*(n-2)$ triangles such that one of the edges of this triangle is $i$.in the other hand the number of such triangles is at most $(n-2)/2*(n-1)$ which is a contradiction.

)

An equivalent formulation of this problem appeared in Hong Kong 2002. See here.

tfw only the construction part of the problem is slightly nontrivial We claim only odd $n$ work. Consider a $K_n$ with edges colored in $n$ colors such that for any $3$ colors, there exists a triangle whose edges are of the three colors. Observe that for any three colors, there exists a unique triangle whose edges are of the three colors. For every color $c$, there are exactly $\binom{n-1}{2}$ triangles containing an edge of color $c$, and each edge of color $c$ is contained in exactly $n-2$ triangles. Thus there are exactly $\frac{n-1}{2}$ edges of each color so $n$ is odd. Now the construction. Let $n=2k+1$. Consider the $K_n$ with vertices $v_1,v_2\ldots,v_{2k+1}$. Edges $v_{i+j}v_{i-j-1}$ where $0\leq j\leq k-1$ are colored with color $i$ (indices taken cyclically). Note that edge $v_{i+j}v_{i-j-1}$ is the same as edge $v_{i+(2k-j)}v_{i-(2k-j)-1}$. For any three colors $a,b,c$, we need to find a unique solution to \begin{align*} a+x&\equiv b-y-1\pmod{2k+1}\\ b+y&\equiv c-z-1\pmod{2k+1}\\ c+z&\equiv a-x-1\pmod{2k+1} \end{align*}(other systems of congruences will yield the same triangle). The unique solution is \begin{align*} x&\equiv b-c+k\pmod{2k+1}\\ y&\equiv c-a+k\pmod{2k+1}\\ z&\equiv a-b+k\pmod{2k+1} \end{align*}which corresponds to a unique triangle.

We will see the problem as a graph Let $C_1, C_2, ..., C_n$ the n colors Let $k$ the number of edges color $C_1$ By the condition of the graph: there are at least ${n \choose 3}$ triangles with different colorationes, but we have exactly ${n \choose 3}$ triangles in the graph $\rightarrow$ Each coloration appears exactly one time and each triangle has a coloration of 3 different colors ....$(F_1)$ Let $A_1 =$ {$w_1, w_2$}, $A_2 =$ {$w_3, w_4$}, ...., $A_k =$ {$w_{2k-1}, w_{2k}$} the edges which are color $C_1$ By $(F_1)$ : $A_1, A_2, ..., A_k$ are disjoint two to two ....$(F_2)$ Let $T$ the set of triangles which have exactly one edge which is color $C_1$ By $(F_2)$: Every $A_i$ has $n-2$ edges which can make a triangle of $T$, so $\lvert T \rvert=k(n-2)$ ....$(i)$ By $(F_1)$: Each triangle of $T$ has a different coloration that depends by the 2 edges which are not color $C_1$ ($n-1$ possible colors), so $\lvert T \rvert= {n-1 \choose 2}$ ....$(ii)$ By $(i)$ and $(ii)$: $k(n-2) = \frac{(n-1)(n-2)}{2} \rightarrow k = \frac{n-1}{2} \rightarrow n-1$ is even $\rightarrow$ $n$ is odd For n odd the problem works with this example: Let $v_1, v_2, ..., v_n$ the vertices of the graph We will work with the subscript of the vertices and the colors in module $n$ Color the edge $v_p v_q$ of the color $C_{\frac{p+q}{2}}$ ($\frac{p+q}{2}$ is always possible in module $n$ because n is odd) Proof of that it works: For each three colors $C_{x_1}, C_{x_2}$ and $C_{x_3}$: The numbers $a \equiv x_1+x_3-x_2\pmod{n}, b \equiv x_1+x_3-x_2\pmod{n}$ and $c \equiv x_1+x_3-x_2\pmod{n}$ satisfy $\frac{a+b}{2} \equiv x_1\pmod{n}$ $\frac{b+c}{2} \equiv x_2\pmod{n}$ $\frac{c+a}{2} \equiv x_3\pmod{n}$ Then the vertices $v_a, v_b$ and $v_c$ form a triangle with edges which are of $C_{x_1}, C_{x_2}$ and $C_{x_3}$ colors Therefore, the answer is n odd

The number of distinguishable triangles with edges all different color is $\tbinom{n}{3}$ and so is the number of $C_3$ subgraphs in a $K_n$. Also, every edge are included in a same amount of triangles, so each color must be used on the same amount of edges. This way we know that even $n$ won't work. Now we show that it is possible for odd $n$. Label the polygon as $A_1A_2\cdots A_n$. Assign one of the color to each of the $A_i$s. Now if $A_i$ is colored as color X, the all edges in the form $A_{i-j}A_{i+j}$ where $1\leq j\leq \frac{n-1}{2}$ would be colored as color X (indices taken mod $n$).