How to prove second part of this combinatorial lemma?

Question

Lemma is stated like this:

Lemma 1. Suppose that a finite number of points subdivides a closed interval into smaller intervals. The left endpoint of the original interval is labeled by 0, the right one by 1, and each of the partitioning points inside the interval is also labeled by either 0 or 1. Then there is an interval of the subdivision whose endpoints are labeled by different numbers. Moreover, the number of such intervals is odd.

I understand existence part, that is, that there is an interval of the subdivision whose endpoints are labeled by different numbers. But I do not understand why the number of such intervals must be odd?

How would you prove that?

Answer 1

If you go from left to right and record the number of times 0 changed to 1 or vice versa, then this number is odd (because you start with 0 and end with 1).

But that number is precisely the number of intervals with different labels.

By the way this is the toy version of Sperner's lemma.

Answer 2

You can use induction to prove that.

Extend the statement by adding that the number of such intervals is even if the points of the original interval are both labeled by $0$ or are both labeled by $1$.

This enforces your induction hypothese and makes things more easy to prove.

The statement is obviously true if $n=0$ points are added.

If $n>0$ points are added then pick out one of these (inner) points.

It splits up the original interval in two intervals with $<n$ points.

Treating them separatedly for both of them the induction hypothese informs you completely about the question whether the number of the special intervals are odd or even.

That leads to the expected conclusions for $n$.