Label sides of a regular $n$-gon in clockwise direction in order 1,2,..,n. Determine all integers n ($n\geq 4$) satisfying the following conditions: (1) $n-3$ non-intersecting diagonals in the $n$-gon are selected, which subdivide the $n$-gon into $n-2$ non-overlapping triangles; (2) each of the chosen $n-3$ diagonals are labeled with an integer, such that the sum of labeled numbers on three sides of each triangles in (1) is equal to the others;
Problem
Source: China Western Mathematical Olympiad 2013, problem 7
Tags: combinatorics unsolved, combinatorics
06.09.2013 13:37
monsterrr wrote: Label sides of a regular $n$-gon in clockwise direction in order 1,2,..,n. Determine all integers n ($n\geq 4$) satisfying the following conditions: (1) $n-3$ non-intersecting diagonals in the $n$-gon are selected, which subdivide the $n$-gon into $n-2$ non-overlapping triangles; (2) each of the chosen $n-3$ diagonals are labeled with an integer, such that the sum of labeled numbers on three sides of each triangles in (1) is equal to the others; Any ideas? Actually, it is easy to show that for all even $n$ and all $n=4k+1$ there exist such $n$-gon...
16.01.2018 00:47
I am pretty sure for even $n$ it doesn't work except $n=4$ and it works for all odd $n$. I think we can construct some sort of parity contradiction.
10.07.2021 23:14
Solved with flashsonic. We claim all $n$ work except $n\equiv 2 \pmod{4}$. It is easy to show that $n\equiv 2 \pmod{4}$ all fail, because if we let $S$ be the sum of all triangle's values, and $D$ be the sum of all diagonals, then \[4\mid n-2 \mid S = \frac{n(n+1)}{2}+2D \equiv 1 \pmod{2}\]Which is a contradiction. $\blacksquare$. We now offer a construction seperately for odd $n$ and for $4\mid n$. Label point $i$ as the point between the segments with value $i-1$ and $i$. For odd $n$, we may construct with a common sum of $(3n+3)/2$. Draw diagonals from $P_1$ to points $P_{2k+1}$ with value $(n-3)/2+(n+1) -k = \frac{3n-1}{2} - k$. Next, draw diagonals from $P_1$ to $P_{2k}$ with value $2-k$. We may verify that this works by considering the sum of $\triangle P_1 P_{2k}P_{2k+1}$ for any $k$. Which will have sum \[(2-k) + (\frac{3n-1}{2}-k) + 2k = \frac{3n+3}{2}\]so this case is done. $\blacksquare$. We now move onto the $4\mid n$ case. Firstly, $\textbf{Claim 1: }$ A polygon with clockwise lengths of $4m-4,4m-4,4m-3,4m-2,4m-1,4m$ satisfies the property that for all integers $V$, it can have its diagonals labelled so that each triangle has value $V$. $\textbf{Proof}$. Write $x=V-8m+3$. Then, fill in the hexagon as follows, which clearly has all triangles with sum $V$. $\blacksquare$. Finally, we will prove with induction that all $4\mid n$ have a diagonalisation that works with sum $V$. The base case $n=4$ is trivial, just arbitrarily label the diagonal that seperates 1,4 from 2,3. Then, for the inductive step simply apply claim 1, which reduces it to the $n-4$ case, which is solvable by the inductive hypothesis. Thus, our induction is complete and we've finished the $4\mid n$ construction. $\blacksquare$. Thus, we've shown that $n\equiv 2 \pmod{4}$ fails, and we've provided a construction for all other $n$, so we're done $\blacksquare$.