A positive integer $n < 2017$ is given. Exactly $n$ vertices of a regular 2017-gon are colored red, and the remaining vertices are colored blue. Prove that the number of isosceles triangles whose vertices are monochromatic does not depend on the chosen coloring (but does depend on $n$.)
Problem
Source: 2018 Thailand TST 1.2
Tags: graph theory, combinatorics, geometry, combinatorial geometry
17.04.2022 10:08
Actually,there are $\frac{3}{2}n(2017-n)$ isosceles triangles which have different colors of vertices.
18.04.2022 13:07
As number of all isosceles triangles are fixed, we will prove instead that the number of non-monochromatic isosceles triangles does not depend on coloring. We will show that if we change $2017$ to any $m\in\mathbb{Z}_{>0}$ such that $\gcd(m,6)=1$ then the number of non-monochromatic triangles are $\frac 32 n(m-n)$. Label each vertex as $1,2,\hdots, m$ in counterclockwise order. We see that three vertices $a,b,c$ will form the isosceles iff $x\equiv\frac{y+z}{2}\pmod m$ for some permutation $(x,y,z)$ of $(a,b,c)$. Let $S$ be a set of sets $\{a,b,c\}$ such that vertices $a,b,c$ form an isosceles triangle, and not all of them have the same color. We use double counting with the number of pairs $(T,e)$ where $T\in S$ and $e$ is an edge that joins vertices with different colors of $T$. For the first way, we see that for any $T\in S$, we can choose exactly $2$ choices of $e$. Thus, the number is equal to $2|T|$. For the second way, we we choose $e=\{a,b\}$ from any pairs of different color vertices first, which has $n(m-n)$ choices. (There are $n$ red vertices and $m-n$ blue vertices.) Then, we choose $c$ such that $\{a,b,c\}\in S$. The only possible choices of $c$ are $2a-b,\frac{a+b}{2},2b-a\pmod m$. Observe that because $a\not\equiv b\pmod m$ and $6\nmid m$, these three numbers are different in modulo $m$. Thus, there are exactly $3$ choices to choose $T$ for each $e$, so the number of pairs $(T,e)$ is $3n(m-n)$. Therefore, $2|S|=3n(m-n)$, yielding that the number of non-monochromatic triangles are exactly $\frac 32n(m-n)$, independent from the way of vertices coloring.