Let $n$ be a natural number. Suppose $A$ and $B$ are two sets, each containing $n$ points in the plane, such that no three points of a set are collinear. Let $T(A)$ be the number of broken lines, each containing $n-1$ segments, and such that it doesn't intersect itself and its vertices are points of $A$. Define $T(B)$ similarly. If the points of $B$ are vertices of a convex $n$-gon (are in convex position), but the points of $A$ are not, prove that $T(B)<T(A)$. Proposed by Ali Khezeli
Problem
Source: Iran TST 2012-Third exam-2nd day-P5
Tags: rotation, inequalities, combinatorial geometry, combinatorics proposed, combinatorics
18.05.2012 09:34
So, in fact, this says that the number $T(S)$ of such broken lines for a set $S$ of $n$ points in general position in the plane has minimum value if and only if the points are in convex position.
18.05.2012 12:18
Yes, it says exactly that. First, notice that if $A$ and $B$ are two convex $n$-gons then $T(A)=T(B)$. Now let $A$ be an arbitrary set of $n$ points. Take all lines connecting any two of these points and take a point $O$ not belonging to any of them. Take a ray with origin in $O$, and let begin to rotate it and enumerate the swept away point of $A$ as $a_1,a_2,\ldots, a_n$. Consider a set $A'$ of $n$ points $1,2,\ldots,n$ on a circumference in exactly that order. So $A'$ is a convex $n$-gon. Let $f: A \to A',\, f(a_i) = i$. Notice that if $m n,\, m_1n_1$ are two segments with end points in $A'$, which do not intersect each other then $f^{-1}(m)f^{-1}(n),\, f^{-1}(m_1)f^{-1}(n_1)$ are two segments with end points in $A$, which also do not intersect each other. It means that if $\ell^{'}$ is a broken line in $A'$ that doesn't intersect itself, then $f^{-1}(\ell^{'})$ will be a broken line in $A$ with the same property. Thus $T(A') \leq T(A)$. Proving that the inequality is strict needs a little bit more effort.
18.05.2012 13:23
dgrozev wrote: If $m n,\, m_1n_1$ are two segments with end points in $A'$, which do not intersect each other then $f^{-1}(m)f^{-1}(n),\, f^{-1}(m_1)f^{-1}(n_1)$ are two segments with end points in $A$, which also do not intersect each other. . Are you sure? [geogebra]498c26cbea279a2d2d7b3a2a0377ad6d6f6fc051[/geogebra]
18.05.2012 14:58
You are right, thanks. I missed this option.
22.05.2012 02:57
Lemma: If $B$ is a convex set of $n$ points then $T(B) = n\cdot 2^{n-3}$ Proof: Work over $\mod n$ and label the vertices clockwise $u_1,u_2,...,u_n$. Suppose a broken line, $\ell$, starts from vertex $u_j$, then the second vertex in that path is $u_{j-1}$ or $u_{j+1}$ otherwise we would ostracise some set of vertices. In general if the vertices that $\ell$ has already reached are $\{u_{i},u_{i+1},...,u_j,...,u_{k}\}$, then the next vertex in the path must be $u_{i-1}$ or $u_{k+1}$. So there are $2^{n-2}$ paths originating from $u_j$, and the conclusion follows $\square$ Let $A$ be any set of $n$ point in the plane such that $|\text{conv}(A)|=m < n$. It will be sufficient to describe a certain subclass of broken lines through $A$. Start at a vertex $u_1\in \text{conv}(A)$, and let $A_1=A\backslash\{u_1\}$. Now $\text{conv}(A_1)$ is a polygon and we can draw at least two edges from $u_1$ to $\text{conv}(A_1)$ that do not intersect an edge of the polygon. Chose one arbitrarily, call it $u_2$ and let $A_2 = A_1 \backslash\{u_2\}$. We repeat this process $n-2$ times until there is only one point left, and then the broken line is uniquely determined. The way we chose the points ensures that none of these broken lines will intersect themselves, furthermore at the $j^{\text{th}}$ step we chose from $2 + \alpha_j$ points. So there are at least $S=\textstyle\prod_{j=1}^{n-2}(2+\alpha_j)$ such lines. Since each point inside the convex hull of $A$ is eventually on the convex hull of some $A_k$ and visible from $u_{k-1}$, we know that $\alpha_1 + ... +\alpha_{n-2} \ge n-m$. So it is clear that $S \ge (2+n-m) 2^{n-3}$. This means there are at least $\textstyle\frac{1}{2}m(2+n-m)2^{n-3}$ broken lines through $A$. By the lemma it is sufficient that $\textstyle\frac{1}{2}m(2+n-m)2^{n-3} > n2^{n-3}$ or equivalently, $(m-2)(n-m) > 0$ But certainly $m=\text{conv}(A) >2$, and $n-m>0$ by the assumption that $A$ is not convex so the claim is proven $\square$
30.05.2012 20:08
My key idea was following lemma: Let $A$ be a set consisting of $n$ point in plane and let $P$ be the point on its convex hull. There are at least $2^{n-2}$ brokes lines such that it starts in $P$, doesn't intersect itself, its vertices are point of $A$ and it contains $n-1$ segments. And equality holds if and only if $A$ is convex. Proof is pretty easy, but really nice. In each step we have to choose next point and it can be every visible point of convex hull of unvisited points. If it's not last step, we have at least 2 choices, so since there are $n-1$ steps, it can be done in at least $2^{n-2}$ ways. And if $A$ isn't convex, in some specific moment we will have at least 3 choices. If $A$ is convex, there is $T(A)=n2^{n-3}$. Now choose one point $Q$ on $B's$ convex hull. And now draw line passing through $Q$, dividing rest of points in two parts (call them $C$ and $D$). Now apply lemma to $C \cup Q$ and $D \cup Q$ and sum it for all possible divisions and we will be done .