Middle European Mathematical Olympiad

Solution:
Fix $n$ points on a plane, no three of which are collinear. Let $\mathcal{P}$ be their convex hull. Let the vertices of $\mathcal{P}$ be $A_{1}, A_{2}, \ldots, A_{m}$ (lying in this order on the boundary of $\mathcal{P}$ counterclockwise). We denote $A_{m+1}=A_{1}$. Also, let $\mathcal{I}$ be the set of our fixed points other than $A_{1}, \ldots, A_{m}$, i.e. the points lying in the interior of $\mathcal{P}$.

Lemma. Every good polyline contains all but one side of $\mathcal{P}$.
Proof. The key observation is that if a segment $A_{i} A_{i+1}$ is not a part of our polyline, then the point $A_{i+1}$ appears in the polyline before $A_{i}$.
This is clear if $A_{i}$ is the last vertex of the polyline. Otherwise there is a segment $A_{i} X$ in the polyline, where $X \neq A_{i+1}$. Observe that all segments appearing after $A_{i} X$ are located in the halfplane determined by the line $A_{i} X$ which does not contain the point $A_{i+1}$. This is because the polyline always turns left, has no self-intersections, and $A_{i}$ is a vertex of $\mathcal{P}$. This implies that the point $A_{i+1}$ must appear in the polyline before $A_{i}$.
It is clear that at least one side of $\mathcal{P}$ does not appear in the polyline. Suppose now that $A_{i_{1}} A_{i_{1}+1}, A_{i_{2}} A_{i_{2}+1}, \ldots, A_{i_{j}} A_{i_{j}+1}$ are all segments on the boundary of $\mathcal{P}$ that do not appear in the polyline (where $1 \leqslant i_{1}<i_{2}<\ldots<i_{j} \leqslant n$ and $j \geqslant 2$ ). Using the observation we know that $A_{i_{1}}$ appears after $A_{i_{1}+1}$, which is followed by $A_{i_{1}+2}, A_{i_{1}+3}, \ldots, A_{i_{2}}$. Since $A_{i_{2}} \neq A_{i_{1}}$, this means that $A_{i_{1}}$ appears after $A_{i_{2}}$. Analogously, $A_{i_{2}}$ appears after $A_{i_{3}}$, and so on, and $A_{i_{j}}$ appears after $A_{i_{1}}$. Thus $A_{i_{1}}$ appears after $A_{i_{1}}$, which is absurd. Therefore there is exactly one $i$ such that $A_{i} A_{i+1}$ does not belong to the polyline.

Lemma. For every good polyline there is a line which intersects exactly one segment of the polyline.
Proof. Using the previous lemma we know that there is exactly one $i$ such that $A_{i} A_{i+1}$ does not belong to the polyline. Thus the polyline is of the form $B_{1} B_{2} \ldots B_{j} A_{i+1} A_{i+2} \ldots A_{i-1} A_{i} C_{1} C_{2} \ldots C_{l}$. (It may happen that there are no points before $A_{i+1}$ and/or no points after $A_{i}$.)
It is quite clear that $B_{1} B_{2} \ldots B_{j} A_{i+1}$ and $A_{i} C_{1} C_{2} \ldots C_{l}$ can be separated by a line. Again, this follows form the fact that polyline has no self-intersections and always turns left, and the fact that you can separate two non-intersecting convex polygons by a line. It is clear that this separating line must intersect exactly one segment of the polyline $A_{i+1} A_{i+2} \ldots A_{i-1} A_{i}$.

Lemma. Each good polyline is uniquely determined by an $i$ such that $A_{i} A_{i+1}$ is not in the polyline and by the partition $\mathcal{I}=\mathcal{B} \cup \mathcal{C}$ such that there is a line intersecting $A_{i} A_{i+1}$ separating $\mathcal{B}$ from $\mathcal{C}$.
Proof. This is easy to see. We use the previous lemma and the fact that the polyline only turns left and has no self-intersections.

Lemma. Consider the $\binom{n-m}{2}$ lines determined by the points of $\mathcal{I}$. Suppose that $j$ of them intersect segment $A_{i} A_{i+1}$. Then there are exactly $n-m+j+1$ good polylines not containing $A_{i} A_{i+1}$.
Proof. We will move a point $X$ along the segment $A_{i} A_{i+1}$, starting from $A_{i}$, and count how many good partitions of $\mathcal{I}$ are there. In the beginning of our journey there are $n-m+1$ possible partitions of $\mathcal{I}$ by a line passing through $X$. Every time we cross a line determined by some two points of $\mathcal{I}$ we get exactly one new partition. Since we cross $j$ such lines, the total number of good partitions is equal to $n-m+1+j$. This corresponds to $n-m+j+1$ good polylines.

Lemma. There are exactly $(n-m+1) m+2\binom{n-m}{2}$ good polylines.
Proof. For each $i$ there are $n-m+j_{i}+1$ good polylines. Summing up yields
$$\sum_{i=1}^{m} n-m+j_{i}+1=m(n-m+1)+\sum_{i=1}^{m} j_{i}=(n-m+1) m+2\binom{n-m}{2}$$
because there are $\binom{n-m}{2}$ lines determined by points in $\mathcal{I}$ and each of them intersects two sides of $\mathcal{P}$.
Since $m \mapsto 2\binom{n-m}{2}+(n-m+1) m$ is decreasing, it follows that the greatest possible number of good polylines is achieved for the smallest possible value of $m$, i.e. for $m=3$. Therefore the answer is $2\binom{n-3}{2}+3(n-2)=n^{2}-4 n+6$.