Iranian Mathematical Olympiad

We call such a broken line a good path.

Lemma. Let $C$ be a set of $n\ge 2$ points in the plane, no three of which are collinear and let $x_0$ be a vertex of the convex hull of $C$. The number of good paths with vertices of $C$ starting at $x_0$ is at least $2^{n-2}$. Equality holds only when $C$ is convex.

Proof. We use induction on $n$. For $n=2$ it is trivial. Suppose the claim is true for $n-1$. Let $x_{0}y$ be a line such that $C-\{x_0\}$ is entirely in one side of it. Sort the vertices of $C-\{x_0\}$ as $x_1,x_2,\dots ,x_{n-1}$ such that the angles $\angle x_i{x}_{0}y$ are increasing. So $C-\{x_0,x_1\}$ is entirely in one side of $x_0{x}_1$ and $C-\{x_0,x_{n-1}\}$ is entirely in one side of $x_0{x}_{n-1}$. There are at least $2\times 2^{n-3}$ good paths with vertices of $C-\{x_0\}$ starting at either $x_1$ or $x_{n-1}$. By joining the segments $x_0{x}_1$ or $x_0{x}_{n-1}$ we obtain at least $2^{n-2}$ good paths with the vertices of $C$ starting at $x_0$.

If $C$ is convex, then in any good path starting at $x_0$, $x_0$ should be joined to $x_1$ or $x_{n-1}$, because in other cases the vertices will be in both sides of the first segment and the path will intersect the first segment. So equality for convex sets follows by the induction hypothesis.

Now, suppose $C$ is not convex. Let $z$ be a vertex of $C$ not on the convex hull. Either $z$ is in triangle $x_0{x}_1{x}_{n-1}$ or is inside the convex hull of $C-\{x_0\}$ (depending on which side of $x_1{x}_{n-1}$ that $z$ is in). In the first case, if $z^{\prime }$ is the farthest vertex from line in triangle $x_0{x}_1{x}_{n-1}$ (other than $x_0$), then the segment $x_0{z}^{\prime }$ doesn't intersect the convex hull of $C-\{x_0\}$ and there is a good path starting with $x_0{z}^{\prime }$ by the induction hypothesis. In the second case, $C-\{x_0\}$ is not convex and the number of good paths starting with $x_0{x}_1$ is more than $2^{n-3}$ by the induction hypothesis. So the lemma is proved. $\square$

According to the lemma, we have $T(B)=n{2}^{n-3}$. We prove $T(A)>n{2}^{n-3}$. Let $x_0$ be a vertex on the convex hull of $A$ and sort the other vertices of $A$ as described in the lemma. For any $1\le i\le n-2$, by joining any two good paths starting at $x_0$ with vertices of $\{x_0,x_1,\dots ,x_i\}$ and $\{x_0,x_{i+1},\dots ,x_{n-1}\}$, we get a good path with the vertices of $A$, because the two sets can be divided by a line through $x_0$. This way we get ${\sum }_{i=1}^{n-2}{2}^{i-1}\times 2^{n-i-2}=(n-2)2^{n-3}$ good vertices not starting at $x_0$. There are more than $2^{n-2}$ good vertices starting at $x_0$ and so $T(A)>n{2}^{n-3}$. So, the assertion is proved. $\square$