1
$\begingroup$

I've been trying to solve the following home task:

Choose $n$ points ($n\ge 2$) on the circle's circumference and connect them all with each other using chords. In result, the circle is divided into $R$ number of regions. Let $P$ be the number of intersection points and $S$ the number of (chord) segments.

Prove that $P-S+R=1$.

A hint is provided that it's not advised nor needed to try and find the exact counts for $P$, $S$ or $R$.

My first insight is that we can always create a regular polygon with $n$ sides if we put the points on circle equally spaced. So for example a pentagon has $P=5$, $S=20$ and $R=16$.

But here I'm stuck badly. Maybe we could apply Euler's polyhedron formula but I don't see how since it's for polyhedrons. The hint makes me think about an inductive approach. But if we start with $n$ points and add one more (that is, go from $n$-gon to ($n+1$)-gon), I don't see how we can make use of the induction assumption to proof the $(n+1)$ case.

Any insight is welcome!

  • 2
    You may use Euler's formula: Imagine that your drawing is placed on the northern half of a sphere and the southern half is an "empty" $n$-gon.2012-05-02

1 Answers 1

1

Here is an idea of a proof, similar to a proof for the Euler's formula:

Pick to adjacent points in the circumference, remove the chord corresponding to these points. Think about how R, S and P change, it is "obvious" that S decreases in 1, R decreases in 1 and P does not change.

This is the base for an inductive proof, you should work out what is the base case for the induction and you should write the "obvious" part above carefully.

EDIT: This does not work as pointed by randomguy in the comment below, but: You can cut the chords at every intersection point, this adds one point and one segment, so the invariant does not change. At the end you have a planar graph and you can apply the Euler's formula. But the comment of Christian Blatter gives a better idea.

  • 0
    Ok, you have a point. I don't know how to fix the idea without copying the proof of the Euler's formula.2012-05-02