Let V={v0,...,vn} and ek:=(vk−1,vk). Given an edge e, let ϕe denote the map that maps the color of the left to that of the right node. Given a k∈{1,...,n}, let ϕk=ϕek∘...∘ϕe1. Let b denote the color blue and g the color green. Let c(k) be 1 if edge ek is bichromatic, and 0 otherwise. Then we need to show that ϕn(b)=g⟹(∑nk=1c(k)) is odd. We’ll show (∑nk=1c(k)) is even⟺ϕn(b)=b, which is a striclty stronger statement than the contrapositive.
For n=1, the LHS is equivalent to c(ϕ1)=1, and indeed ϕ(e1)(b) equals g if e1 is bichromatic, and b otherwise. Now let n>1 and let it be true for n−1. Suppose ∑nk=1c(k) is even. Then, if c(en)=1, that means (∑n−1k=1c(k)) is odd, so that ϕn(b)=ϕen(ϕn−1(b))=ϕen(g)=b, and if c(en)=0, then (∑n−1k=1c(k)) is even, so that ϕn(b)=ϕen(ϕn−1(b))=ϕen(b)=b. Now suppose ∑nk=1c(k) is odd. If c(en)=1, then (∑n−1k=1c(k)) is even, so that ϕn(b)=ϕen(ϕn−1(b))=ϕen(b)=g, and if c(en)=0, then (∑n−1k=1c(k)) is odd, so that ϕn(b)=ϕen(ϕn−1(b))=ϕen(g)=g. This proves the lemma by induction.
Ex 2
Ordinarily I’d proof by contradiction, using sequences, that inf{x∈[0,1]|f(x)>0} can neither be greater nor smaller than 0. I didn’t manage a short way to do it using the two lemmas, but here’s a long way.
Set x0=0. Given n∈N+, let Gn be a path graph of n+1 vertices {vn,0,...,vn,n}, where vn,k=kn. If for any n and k we have f(vn,k)=0, then we’re done, so assume we don’t. Define c(v,v′) to be 1 if f(v) and f(v′) have s different sign, and 0 otherwise. Sperner’s Lemma says that the number of edges e with c(e)=1 are odd; in particular, there’s at least one. Let the first one be denoted (v,w), then set xn=max{v,xn−1}.
Now consider the sequence (xn)n∈N. It’s bounded because xk∈[0,1]. Using the Bolzano-Weierstrass theorem, let (x′n)n∈N↦x∗ be a convergent subsequence. Since f(xk)>0 for all k∈N+, we have f(x∗)≥0. On the other hand, if f(x∗)>0, then, using continuity of f, we find a number x′>x∗ such that f(x∗,x′)>0. Choose n and k such that vn,k∈(x∗,x′), then c(vn,j)=0 for all j<k, so that xn≥vn,k>x∗ and then xℓ≥xn for all ℓ≥k, so that x∗≥xn≥vn,k>x∗, a contradiction.
Ex 3
Given such a function f, let g:[0,1]↦[−1,1] be defined by g(x)=f(x)−x. We have g(0)=f(0)−0≥0≥f(1)−1=g(1). If either inequality isn’t strict, we’re done. Otherwise, g(0)>0>g(1). Taking for granted that the intermediate value theorem generalizes to this case, find a root x∗ of g, then f(x∗)=f(x∗)−x∗+x∗=g(x∗)+x∗=x∗.
(v,w) is defined just for one particular graph. It’s the first edge in that graph such that f(v)<0<f(w). (So it could have been called (vn,wn)). Then for the next graph, it’s a different v. Basically, x1 looks at where the first graph skips over the zero mark, then picks the last vertex before that point, then x2 looks at the next larger graph, and if that graph skips later, it updates to the last vertex before that point in that graph, etc. I think the reason I didn’t add indices to (v,w) was just that there ar ealready the v with two indices, but I see how it can be confusing since having no index makes it sound like it’s the same value all throughout.
Ex 1
Let V={v0,...,vn} and ek:=(vk−1,vk). Given an edge e, let ϕe denote the map that maps the color of the left to that of the right node. Given a k∈{1,...,n}, let ϕk=ϕek∘...∘ϕe1. Let b denote the color blue and g the color green. Let c(k) be 1 if edge ek is bichromatic, and 0 otherwise. Then we need to show that ϕn(b)=g⟹(∑nk=1c(k)) is odd. We’ll show (∑nk=1c(k)) is even⟺ϕn(b)=b, which is a striclty stronger statement than the contrapositive.
For n=1, the LHS is equivalent to c(ϕ1)=1, and indeed ϕ(e1)(b) equals g if e1 is bichromatic, and b otherwise. Now let n>1 and let it be true for n−1. Suppose ∑nk=1c(k) is even. Then, if c(en)=1, that means (∑n−1k=1c(k)) is odd, so that ϕn(b)=ϕen(ϕn−1(b))=ϕen(g)=b, and if c(en)=0, then (∑n−1k=1c(k)) is even, so that ϕn(b)=ϕen(ϕn−1(b))=ϕen(b)=b. Now suppose ∑nk=1c(k) is odd. If c(en)=1, then (∑n−1k=1c(k)) is even, so that ϕn(b)=ϕen(ϕn−1(b))=ϕen(b)=g, and if c(en)=0, then (∑n−1k=1c(k)) is odd, so that ϕn(b)=ϕen(ϕn−1(b))=ϕen(g)=g. This proves the lemma by induction.
Ex 2
Ordinarily I’d proof by contradiction, using sequences, that inf{x∈[0,1]|f(x)>0} can neither be greater nor smaller than 0. I didn’t manage a short way to do it using the two lemmas, but here’s a long way.
Set x0=0. Given n∈N+, let Gn be a path graph of n+1 vertices {vn,0,...,vn,n}, where vn,k=kn. If for any n and k we have f(vn,k)=0, then we’re done, so assume we don’t. Define c(v,v′) to be 1 if f(v) and f(v′) have s different sign, and 0 otherwise. Sperner’s Lemma says that the number of edges e with c(e)=1 are odd; in particular, there’s at least one. Let the first one be denoted (v,w), then set xn=max{v,xn−1}.
Now consider the sequence (xn)n∈N. It’s bounded because xk∈[0,1]. Using the Bolzano-Weierstrass theorem, let (x′n)n∈N↦x∗ be a convergent subsequence. Since f(xk)>0 for all k∈N+, we have f(x∗)≥0. On the other hand, if f(x∗)>0, then, using continuity of f, we find a number x′>x∗ such that f(x∗,x′)>0. Choose n and k such that vn,k∈(x∗,x′), then c(vn,j)=0 for all j<k, so that xn≥vn,k>x∗ and then xℓ≥xn for all ℓ≥k, so that x∗≥xn≥vn,k>x∗, a contradiction.
Ex 3
Given such a function f, let g:[0,1]↦[−1,1] be defined by g(x)=f(x)−x. We have g(0)=f(0)−0≥0≥f(1)−1=g(1). If either inequality isn’t strict, we’re done. Otherwise, g(0)>0>g(1). Taking for granted that the intermediate value theorem generalizes to this case, find a root x∗ of g, then f(x∗)=f(x∗)−x∗+x∗=g(x∗)+x∗=x∗.
On your Ex. 2:
Is there something I’m missing? It seems to me that xn=v for all n>1.
(v,w) is defined just for one particular graph. It’s the first edge in that graph such that f(v)<0<f(w). (So it could have been called (vn,wn)). Then for the next graph, it’s a different v. Basically, x1 looks at where the first graph skips over the zero mark, then picks the last vertex before that point, then x2 looks at the next larger graph, and if that graph skips later, it updates to the last vertex before that point in that graph, etc. I think the reason I didn’t add indices to (v,w) was just that there ar ealready the v with two indices, but I see how it can be confusing since having no index makes it sound like it’s the same value all throughout.