$n$ positive numbers are given. Is it always possible to find a convex polygon with $n+3$ edges and a triangulation of it so that the length of the diameters used in the triangulation are the given $n$ numbers? Proposed by Morteza Saghafian
Problem
Source: Iran TST1 Day 2 P6
Tags: combinatorics, triangulation, Iranian TST, Morteza Saghafiyan
24.02.2020 06:23
I believe the answer is yes. For $n \le 2$, the answer is trivially yes. Suppose from now on that $n \ge 3.$ Call the $n$ numbers $a_1, a_2, \cdots, a_n$. WLOG let the $a_i$'s be greater than $1000$ by scaling. Let $\sum \sqrt{a_i^2 - 1} = x,$ and consider a $1 \times x$ rectangle $ABCD$ with $AB = CD = x$. Select an arbitrarily large positive integer $y > (100x)^{10^{10^{10}}}$ and consider the circles $\omega, \Omega$ with radius $y$ satisfying the following conditions. The center of $\omega$ (resp. $\Omega$) is on the same side of $AB$ (resp. $CD$) as points $C$ and $D$ (resp. points $A$ and $B$), and passes through $A, B$ (resp. $C, D$). Let $\Gamma$ denote the shape which is bounded by the sides $BC, AD$ and the circles $\omega, \Omega.$ Now, mark points $P_1, P_2, \cdots, P_{n+1}$ on the boundary of the $1 \times x$ rectangle such that $P_1 = A$ and $P_i P_{i+1} = a_i$ for each $1 \le i \le n.$ Now, by selecting a point $P_0$ arbitrarily close to the midpoint of $P_1 P_2$ which is on the opposite side of $P_1P_2$ as $P_3$, and selecting a point $P_{n+2}$ arbitrarily close to the midpoint of $P_n P_{n+1}$ which is on the opposite side of $P_n P_{n+1}$ as $P_{n-1}$, we have our convex polygon $P_0 P_1 \cdots P_n P_{n+1} P_{n+2}.$ Now, the diagonals $P_1 P_2, P_2 P_3, \cdots, P_n P_{n+1}$ comprise the desired triangulation. $\square$
24.02.2020 18:48
If diameter simply means the length of diagonals, I think this was too easy for Iranian TST #6. For given $a_1 < a_2 < ... < a_n$ we can always construct some convex $n+1$-gon $P P_1 ... P_n$ with $P P_i = a_i$. This can be done by induction. When $n=2$, it is obvious. Next when new $a_0$ is given so that $a_0 < a_1 < ... <a_n$, first construct convex $n+1$-gon $PP_1P_2...P_n$ by induction hypothesis for $a_1<...<a_n$. Since $\angle P_2 P_1 P$ which is less than $\pi$, we can place $P_0$ with $\angle P_0 P_1 P$ is less than $\pi - \angle P_2 P_1 P$ and $P P_0 = a_0$. Note that $\angle P_0 P P_1$ can be simultaneously adjusted so that $\angle P_0 P P_n$ is still less than $\pi$. Therefore, again $P P_0 ...P_n$ is convex. Back to question take additional two positive number $a,b$ such that the interval $(a,b)$ contains all the $n$ numbers. Then construct convex $n+3$-gon inductively and done. Remark) This proof assumed all the numbers are different but I think still we can simply adjust this and make it true when repetition of numbers is allowed.
25.02.2020 01:50
@above I haven't found an easy way to make adjustments in the case where repetition is allowed. If only one number has multiplicity greater than one (appears multiple times among the $a_i$'s) then we can still make it work by "switching vertices." In other words, we can do it where all diagonals contain one of two vertices. However, when there are many numbers which appear multiple times I'm not sure it's easy to do anymore. Do you have a way to take care of this scenario?
25.02.2020 04:09
Thanks for comment! I would try.
16.03.2020 00:48
When all lengths are distinct the problem is trivial. Suppose we are given : $p_1$ times length $d_1$ , $p_2$ times length $d_2$ ,..., $p_k$ times length $d_k$ and $d_1>d_2>...>d_k$ Firstly: make for each length $ d_i $ a bundle$[i]$ of the $p_i$ segments sharing a common vertex $A_i$ and require that it is really thin namely the angle (place the bundle vertically) between the leftmost ($A_iX_{i-1}$)and rightmost ($A_iX_i$) segment is small enough such that the following configuration is part of a triangulated convex polygon. We want to place the $k$ bundles in order , bundle$[1]$ then bundle$[2]$ etc. ,such that consecutive ones coincide at point $X_i$ and the following are satisfied: The angle at $X_i$ is convex. The angle $A_iA_{i+1}A_{i+2}$ is convex. Suppose that we already have placed bundle$[1]$ ,..., bundle$[n]$ When placing bundle$[n+1]$ observe that if : $A_nX_nA_{n+1}$ is sufficiently small then the angle at $X_n$ is definetely convex and at the same time $A_{n-1}A_nA_{n+1}$ is convex If angle $A_nX_{n+1}A_{n+1}$ is sufficiently we can keep doing this and hence this construction is possible.
02.07.2020 19:55
It seems that the word "diameter" is ambiguous. I've read the original test paper, which used the word "قطر" (qotr). According to the Persian wiki: https://fa.wikipedia.org/wiki/%D9%82%D8%B7%D8%B1_(%D9%87%D9%86%D8%AF%D8%B3%D9%87). this word means the segment connecting the two non-adjacent vertex in a polygon, which is the diagonal as I thought. It's a little weird that this problem is a P6 in Iran TST...
12.02.2023 06:42
Any body got the official answer¿