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?

 

Advertisements
Points on the unit circle

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s