# Points on the unit circle

This problem is from Stanley’s “Enumerative Combinatorics Vol. I”, more precisely problem 12 from Chapter 1 (sadly, no solution is provided there.)

Consider $n$ points arranged in the unit circumference and draw all $\binom n2$ chords connecting two of the points. Assume that the points are laid out in such a way no three chords intersect in a single point (that is, there are no triple intersections). Into how many regions will the interior of the circle by divided? Stanley says: “Try to give an elegant proof avoiding induction, finite differences, generating functions, summations, and the like.” One can do such a thing.

There’s another problem that involves placing points in the circle. Place $2n$ points in the circle, and label $n$ of them with a $1$, and the remaining $n$ with a $-1$. Prove we can trace the circle, starting from on of this points, in such a way that the partial sums of the values of the points is always positive, and this can be done both clockwise and anticlockwise. Can you generalize this to a continuous (as opposed to discrete) setting?

## 2 thoughts on “Points on the unit circle”

1. First problem: forgetting about the $n$ exterior faces we obtain a planar graph with say $v$ vertices, $f$ faces, and $e$ edges. We’re trying to find $f+n$. The construction ensures there are $v-n$ vertices of degree four, and $n$ vertices of degree $n-1$. Thus $2e=n(n-1)+4(v-n)$, or what is the same, $e=\binom n2 + 2 (v-n)$. I claim there are $\binom n4$ vertices of degree four. Indeed, any such vertex determines four distinct points $i,j,kl$ in the circle, corresponding to a unique $4$-subset of $n$, and viceversa. Note that when $n=1,2,3$, there are no such intersections, and the binomial is indeed zero. Euler’s formula now gives

$v-e+f=(v-n)-\binom n2-2(v-n)+(f+n)=$

$\binom n4-\binom n2-2\binom n4 + f+n=1$

which is the same as $f+n=\binom n4+\binom n2+1$.

Like

2. Second problem: Pick an arbitrary point and consider the function $f(k)$ that moves clockwise $k$ steps, performing the sum of the values of the points traced. Thus $f(0)=f(2n)=0$. This functions then achieves a minimum at some $0 < k_0 < 2n$, and the shifted function $f(k)-f(k_0)$ is our solution. The continuous analogue is the following: pick a function $f:S^1\to\Bbb R$ that integrates to $0$. There is then a point $t_0\in S^1$ such that $F(t)=\int_{t_0}^t f$ remains nonzero.

Like