Topological Fixed Point Exercises
This is one of three sets of fixed point exercises. The first post in this sequence is here, giving context.
(1D Sperner’s lemma) Consider a path built out of edges as shown. Color each vertex blue or green such that the leftmost vertex is blue and the rightmost vertex is green. Show that an odd number of the edges will be bichromatic.

(Intermediate value theorem) The BolzanoWeierstrass theorem states that any bounded sequence in has a convergent subsequence. The intermediate value theorem states that if you have a continuous function such that and , then there exists an such that . Prove the intermediate value theorem. It may be helpful later on if your proof uses 1D Sperner’s lemma and the BolzanoWeierstrass theorem.

(1D Brouwer fixed point theorem) Show that any continuous function has a fixed point (i.e. a point with ). Why is this not true for the open interval ?

(2D Sperner’s lemma) Consider a triangle built out of smaller triangles as shown. Color each vertex red, blue, or green, such that none of the vertices on the large bottom edge are red, none of the vertices on the large left edge are green, and none of the vertices on the large right edge are blue. Show that an odd number of the small triangles will be trichromatic.
Color the all the points in the disk as shown. Let be a continuous function from a closed triangle to the disk, such that the bottom edge is sent to nonred points, the left edge is sent to nongreen points, and the right edge is sent to nonblue points. Show that sends some point in the triangle to the center.

Show that any continuous function from closed triangle to itself has a fixed point.

(2D Brouwer fixed point theorem) Show that any continuous function from a compact convex subset of to itself has a fixed point. (You may use the fact that given any closed convex subset of , the function from to which projects each point to the nearest point in is well defined and continuous.)

Reflect on how nonconstructive all of the above fixedpoint findings are. Find a parameterized class of functions where for each , , and the function is continuous, but there is no continuous way to pick out a single fixed point from each function (i.e. no continuous function such that is a fixed point of for all ).

(Sperner’s lemma) Generalize exercises 1 and 4 to an arbitrary dimension simplex.

(Brouwer fixed point theorem) Show that any continuous function from a compact convex subset of to itself has a fixed point.

Given two nonempty compact subsets , the Hausdorff distance between them is the supremum over all points in either subset of the distance from that point to the other subset. We call a set valued function a continuous Hausdorff limit if there is a sequence of continuous functions from to whose graphs, , converge to the graph of , , in Hausdorff distance. Show that every continuous Hausdorff limit from a compact convex subset of to itself has a fixed point (a point such that ).

Let and be nonempty compact convex subsets of . We say that a set valued function, is a Kakutani function if the graph of , , is closed, and is convex and nonempty for all . For example, we could take and to be the interval , and we could have send each to , map to the whole interval , and map to . Show that every Kakutani function is a continuous Hausdorff limit. (Hint: Start with the case where is a unit cube. Construct by breaking into small cubes of side length . Constuct a smaller cube of side length within each cube. Send each small to the convex hull of the images of all points in the cube with a continuous function, and glue these together with straight lines. Make sure you don’t accidentally get extra limit points.)

(Kakutani fixed point theorem) Show that every Kakutani function from a compact convex subset of to itself has a fixed point.
Please use the spoilers feature—the symbol ‘>’ followed by ‘!’ followed by space in your comments to hide all solutions, partial solutions, and other discussions of the math. The comments will be moderated strictly to hide spoilers!
I recommend putting all the object level points in spoilers and leaving metadata outside of the spoilers, like so: “I think I’ve solved problem #5, here’s my solution <spoilers>” or “I’d like help with problem #3, here’s what I understand <spoilers>” so that people can choose what to read.
 Fixed Point Exercises by 17 Nov 2018 1:39 UTC; 50 points) (
 Fixed Point Discussion by 24 Nov 2018 20:53 UTC; 36 points) (
 4 Aug 2019 23:04 UTC; 15 points) 's comment on Open & Welcome Thread—August 2019 by (
Proof of #4, but with unnecessary calculus:
Not only is there an odd number of tricolor triangles, but they come in pairs according to their orientation (RGB clockwise/anticlockwise). Proof: define a continuously differentiable vector field on the plane, by letting the field at each vertex be 0, and the field in the center of each edge be a vector of magnitude 1 pointing in the direction R>G>B>R (or 0 if the two adjacent vertices are the same color). Extend the field to the complete edges, then the interiors of the triangles by some interpolation method with continuous derivative (eg. cosine interpolation).
Assume the line integral along one unit edge in the direction R>G or G>B or B>R to be ^{1}⁄_{3}. (Without loss of generality since we can rescale the graph/vectors to make this true). Then a similar parity argument to Sperner’s 1d lemma (or the FTC) shows that the clockwise line integral along each large edge is ^{1}⁄_{3}, hence the line integral around the large triangle is 1/3+1/3+1/3=1.
By green’s theorem, this is equal to the integrated curl of the field in the interior of the large triangle, and hence equal (by another invocation of green’s theorem) to the summed clockwise line integrals around each small triangle. The integrals around a unicolor or bicolor triangle are 0 and −1/3 + ^{1}⁄_{3} + 0 = 0 respectively, leaving only tricolor triangles, whose integral is again 1 depending on orientation. Thus: (tricolor clockwise)  (tricolor anticlockwise) = 1. QED.
Generalized to n dimensions in my reply to Adele Lopez’s solution to #9 (without any unnecessary calculus :)
As a physicist, this is my favorite one for obvious reasons :)
Just to get things started, here’s a proof for #1:
Proof by induction that the number of bicolor edges is odd iff the ends don’t match. Base case: a single node has matching ends and an even number (zero) of bicolor edges. Extending with a nonbicolor edge changes neither condition, and extending with a bicolor edge changes both; in both cases the induction hypothesis is preserved.
Here’s a more conceptual framing:
If we imagine blue as labelling the odd numbered segments and green as labelling the even numbered segments, it is clear that there must be an even number of segments in total. The number of gaps between segments is equal to the number of segments minus 1, so it is odd.
Cleanest solution I can find for #8:
ft(x)=11+e10(t−x)
Also, if we have a proof for #6 there’s a pleasant method for #7 that should work in any dimension:
We take our closed convex set S that has the bounded function h:S→S . We take a triangle T that covers S so that any point in S is also in T .
Now we define a new function h′:T→T such that h′(x)=h(cs(x)) where cs(x) is the function that maps x to the nearest point in S.
By #6 we know that h′ has a fixed point, since cs is continuous. We know that the fixed point of h′ cannot lie outside S because the range of h′ is S. This means h′ has a fixed point within S and since for x∈S, h(x)=h′(x), h has a fixed point.
On my approach:
I constructed a large triangle around the convex shape with the center somewhere in the interior. I then projected each point in the convex shape from the center towards the edge of the triangle in a proportional manner. ie. The center stays where it is, the points on the edge of the convex shape are projected to the edge of the triangle and a point 1/x of the distance from the center to the edge of the convex shape is 1/x of the distance from the center to the edge of the triangle.
If #4 is true, it is provable:
If #4 is true, changing the color of a single node (except to forbidden colors on edges) cannot change the parity of the trichromatic triangle count, and this would be checkable through a finite case analysis of graphs of size <=7. Given that lemma, we can recolor one corner to red, the remainder of one large edge blue and the remaining nodes green, producing the odd count 1.
#8:
We are looking for a surface [0,1]²>[0,1] whose intersection with the plane x=y does not contain a function of t. It suffices to show that the intersection looks like the letter s, with exactly the endpoints reaching t=0 or t=1. It suffices to show that the intersection can be any continous function of x including the points t=x=y=0 and t=x=y=1. Within each plane of constant x, define the surface as 0 for small t, 1 for large t, and rapidly rising through the plane x=y wherever we want the intersection.
Found a nice proof for Sperner’s lemma (#9):
First some definitions. Call a dsimplex with vertices colored in (d+1) different colored chromatic. Call the parity of the number of chromatic simplices the chromatic parity.
It’s easier to prove the following generalization: Take a complex of dsimplices that form a dsphere: then any (d+1)coloring of the vertices will have even chromatic parity.
Proof by induction on d:
Base d=1: vacuously true.
Assume true for d1: Say you have an arbitrary complex of dsimplices forming a dsphere, with an arbitrary d+1coloring. Choose a vertex. W.L.O.G. we will call the color of the chosen vertex blue.
Take the complex of simplices that contain this vertex. Since a sphere has no boundary or branches, this complex will be a dball. Delete the chosen vertex, and keep only the opposite (d1)simplices that are left, which will form a (d1)sphere, call it the shell.
We need to choose a second color, say red. We’ll call a (d1)simplex with vertices of all d+1 colors except red an Rchromatic face, and similarly with blue.
Now, replace all the red vertices in the shell with blue vertices, so that the shell is now Rchromatic. By induction it has an even number of Rchromatic faces. Consider what happens when we reconvert a vertex on the shell back to red: since the vertex was previously blue, any Rchromatic faces will get turned into Bchromatic faces. Let r be the number of Rchromatic faces on the shell, and b be the number of Bchromatic faces. The parity of rb will remain even as we continue this process.
Let’s go back to the vertex in the center of the shell. All currently chromatic simplices with this vertex have opposite faces which are Bchromatic, since this vertex is blue. We’ll flip the vertex to red, which destroys chromatic simplices with opposite Bchromatic faces and creates chromatic simplices with opposite Rchromatic faces. Since rb is even, the chromatic parity is preserved!
Since we’ve shown that arbitrary recoloring of vertices preserves the chromatic parity, it’s clear that the chromatic parity will be even for any coloring.
Corollary: Sperner’s lemma
Start with a dsimplex which has been divided into dsimplices, and where each face of the large simplex has one color which vertices on it are forbidden from taking. Take a point of each color, and match it with a face of the simplex that that color is allowed on. Then connect that vertex to each point on that face. This will create a bunch of nonchromatic simplices. Finally, create a simplex of all of the new points. This will create one chromatic simplex.
This will form a dsphere, and thus will have an even chromatic parity. That means the original simplex must have had odd chromatic parity.
Thanks! I find this approach more intuitive than the proof of Sperner’s lemma that I found in Wikipedia. Along with nshepperd’s comment, it also inspired me to work out an interesting extension that requires only minor modifications to your proof:
dspheres are orientable manifolds, hence so is a decomposition of a dsphere into a complex K of dsimplices. So we may arbitrarily choose one of the two possible orientations for K (e.g. by choosing a particular simplex P in K, ordering its vertices from 1 to d + 1, and declaring it to be the prototypical positively oriented simplex; when d = 2, P could be a triangle with the vertices going around counterclockwise when you count from 1 to 3; when d = 3, P could be a tetrahedron where, if you position your right hand in its center and point your thumb at the 1vertex, your fingers curl around in the same direction in which you count the remaining vertices from 2 to 4). Then any ordering of the vertices of any dsimplex in K may be said to have positive or negative orientation (chirality). (E.g. it would be positive when there’s an orientationpreserving map (e.g. a rotation) sending each of its vertices to the correspondingly numbered vertices of P.)
So here’s my extension of parent comment’s theorem: Any coloring of the vertices of K with the colors {1, …, d + 1} will contain an equal number of positively and negatively oriented chromatic dsimplices—that is, the reason the number of chromatic dsimplices in K must be even is that each one can be paired off with one of the opposite (mirror) orientation. (Does this theorem have a name? If so I couldn’t find it.)
Following parent comment, the proof is by induction on the dimension d. When d = 1, K is just a cycle graph with vertices colored 1 or 2. As we go around clockwise (or counterclockwise), we must traverse an equal number of 1→2 edges and 2→1 edges (i.e. oppositely oriented 1simplices), by the time we return to our starting point.
Now let d > 1, and assume the theorem is true in the (d1)dimensional case. As in parent comment, we may choose any vertex v of K, and then the faces opposite to v in each dsimplex in K that contains v will, together, form a (d1)dimensional subcomplex K′ of K that is homeomorphic (topologically equivalent) to a (d1)sphere.
Suppose v has color i. We will show that changing v’s color to j ≠ i will add or remove the same number of positively oriented chromatic dsimplices as negatively oriented ones: Forget, for the moment, the distinction between colors i and j—say any i or jcolored vertex of K′ has color “iorj.” Then K′ is now dcolored, so, by inductive hypothesis, the chromatic (d1)simplices of K′ must occur in pairs of opposite orientation (if any exist—if none exist, v can’t be part of any chromatic dsimplex regardless of its color). Consider such a pair, call them F₁ and F₂.
Now cease pretending that i and j are a single color. Since F₁ was chromatic in K′, it must have had an iorj–colored vertex. Suppose, WOLOG, that that vertex was actually jcolored. Then, together with icolored v, F₁ spans a chromatic dsimplex of K, call it S₁, which we may assume WOLOG to be positively oriented. Once we change the color of v from i to j, however, S₁ will have two jcolored vertices, and so will no longer be chromatic. To see that balance is maintained, consider what happens with F₂:
If F₂‘s iorj–colored vertex was, like F₁‘s, actually jcolored, then the dsimplex spanned by F₂ and v, call it S₂, was chromatic and negatively oriented (because F₂ had opposite orientation to F₁ in K′), and thus S₂ also ceased to be chromatic when we changed v’s color from i to j, balancing S₁‘s loss of chromatic status. Otherwise, F₂‘s iorj–colored vertex must have been icolored, in which case S₂ wasn’t chromatic when v was also icolored, but changing v’s color to j turned S₂ into a new dchromatic simplex. But what is S₂‘s orientation? Well, it was negative under the assumption that S₂‘s iorj–colored vertex was jcolored and v was icolored, and swapping the labels of a pair of vertices in an oriented simplex reverses its orientation, so, under the present assumption, S₂’s orientation must be positive! Thus the loss of S₁ as a positively oriented chromatic dsimplex is balanced by the addition of S₂ as a new positively oriented chromatic dsimplex.
If all of K’s vertices are the same color, it has the same number (zero) of positively and negatively oriented chromatic dsimplices, and since this parity is preserved when we change the colors of the vertices of K one at a time, it remains no matter how we (d+1)color K. ☐
We can relate this theorem back to Sperner’s lemma using the same trick as parent comment: Suppose we are given a triangulation K of a regular dsimplex S into smaller dsimplices, and a (d+1)coloring of K’s vertices that assigns a unique color to each vertex v of S, and doesn’t use that color for any of K’s vertices lying on the face of S opposite to v. We form a larger simplicial complex L containing K by adding d + 1 new vertices as follows: For i = 1, …, d + 1, place a new icolored vertex exterior to S, some distance from the center of S along the ray that goes through the icolored vertex of S. Connect this new vertex to each vertex of K lying in the face of S opposite from the (i+1)colored (or 1colored, when i = d + 1) vertex of S. (Note that none of the dsimplices thereby created will be chromatic, because they won’t have an (i+1)colored vertex.) Then connect all of the new vertices to each other.
Having thus defined L, we can embed it in a dsphere, of which it will constitute a triangulation, because the new vertices will form a dsimplex T whose “interior” is the complement of L in the sphere. Thus we can apply our above theorem to conclude that L has equally many positively and negatively oriented chromatic dsimplices. By construction, none of L’s new vertices are included in any chromatic dsimplex other than T, so K must contain an equal number (possibly zero) of positively and negatively oriented chromatic dsimplices, plus one more, of opposite orientation to T. And what is the orientation of T? I claim that it is opposite to that of S: Consider T by itself, embedded in the sphere. T’s boundary and exterior (the interior of L) then constitute another chromatic dsimplex, call it U, which is essentially just a magnification of S, with correspondingly colored vertices, and so share’s S’s orientation. Applying our theorem again, we see that T and U must have opposite orientations*, so we conclude that K must contain exactly one more chromatic dsimplex of the same orientation as S than of the opposite orientation. (As proved in nshepperd’s comment for the case d = 2.)
*The observation, that, on the surface of a sphere, the interior and exterior of a trichromatic triangle have opposite orientations, is what sent me down this rabbit hole in the first place. :)
Awesome! I was hoping that there would be a way to do this!
Clarifying question for #9:
How does the decomposition into segments/triangles generalize to 3+ dimensions? If you try decomposing a tetrahedron into multiple tetrahedra, you actually get 4 tetrahedra and 1 octahedron, as shown here.
EDIT: answered my own question:
You can decompose an octahedron into 4 tetrahedrons. They’re irregular, but this is actually fine for the purpose of the lemma.
Inappropriately highbrow proof of #4 (2d Sperner’s lemma):
This proves a generalization: any number of dimensions, and any triangulation of the simplex in question. So, the setup is as follows. We have an ndimensional simplex, defined by n+1 points in ndimensional space. We colour the vertices with n+1 different colours. Then we triangulate it—chop it up into smaller simplexes—and we extend our colouring somehow in such a way that the vertices on any face (note: a face is the thing spanned by any subset of the vertices) of the big simplex are coloured using only the colours from the vertices that span that face. And the task is to prove that there are an odd number of little simplexes whose vertices have all n+1 colours.
This colouring defines a map from the vertices of the triangulation to the vertices of the big simplex: map each triangulationvertex to the simplexvertex that’s the same colour. We can extend this map to the rest of each little simplex by linear interpolation. The resulting thing is continuous on the whole of the big simplex, so we have a continuous map (call it f) from the big simplex to itself. And we want to prove that we have an odd number of little simplices whose image under f spans the whole thing. (Call these “good” simplices.)
We’ll do it with two ingredients. The easy one is induction: when proving this in n dimensions we shall assume we already proved it for smaller numbers of dimensions. The harder one is homology, a standard tool in algebraic topology. More precisely we’ll do homology mod 2. It associates with each topological space X and each dimension d an abelian group Hd(X), and the key things you need to know are (1) that if you have f : X → Y then you get an associated group homomorphism f* : Hd(X) → Hd(Y), (2) that Hd(a simplex) is the cyclic group of order 2 if d=0, and the trivial group otherwise, and (3) that Hd(the boundary of a simplex) is the cyclic group of order 2 if d=0 or d = (dimension of simplex − 1) and the trivial group otherwise. Oh, and one other crucial thing: if you have f : X → Y and g : Y → Z then (gf)* = g*f*: composition of maps between topological space corresponds to composition of homomorphisms between their homology groups.
(You can do homology “over” any commutative ring. The groups you get are actually modules over that ring. It happens that the ring of integers mod 2 is what we want to use. A simplex is, topologically, the same thing as a ball, and its boundary the same thing as a sphere.)
OK. So, first of all suppose not only that the number of good simplices isn’t odd, but that it’s actually zero. Then f maps the whole of our simplex to its boundary. Let’s also consider the rather boring map g from the boundary to the whole simplex that just leaves every point where it is. Now, if the thing we’re trying to prove is true in lower dimensions then in particular the map gf—start on the boundary of the simplex, stay where you are using g, and then map to the boundary of the simplex again using f—has an image that, so to speak, covers each boundary face of the simplex an odd number of times. This guarantees—sorry, I’m eliding some details here—that (gf)* (from the cyclic group of order 2 to the cyclic group of order 2) doesn’t map everything to the identity. But that’s impossible, because (gf)*=g*f* and the map f* maps to Hn(whole simplex) which is the trivial group.
Unfortunately, what we actually need to assume in order to prove this thing by contradiction is something weaker: merely that the number of good simplices is even. We can basically do the same thing, because homology mod 2 “can’t see” things that happen an even number of times, but to see that we need to look a bit further into how homology works. I’m not going to lay it all out here, but the idea is that to build the Hd(X) we begin with a space of things called “chains” which are like linear combinations (in this case over the field with two elements) of bits of X, we define a “boundary” operator which takes combinations of ddimensional bits of X and turns them into combinations of (d1)dimensional bits in such a way that the boundary of the boundary of anything is always zero, and then we define Hd(x) as a quotient object: (ddimensional things with zero boundary) / (boundaries of d+1dimensional things). Then the way we go from f (a map of topological spaces) to f* (a homomorphism of homology groups) is that f extends in a natural way to a map between chains, and then it turns out that this map interacts with the boundary operator in the “right” way for this to yield a map between homology groups. And (getting, finally, to the point) if in our situation the number of good simplices is even, then this means that the map of chains corresponding to f sends anything in n dimensions to zero (essentially because it means that the interior of the simplex gets covered an even number of times and when working mod 2, even numbers are zero), which means that we can think of f* as mapping not to the homology groups of the whole simplex but to those of its boundary—and then the argument above goes through the same as before.
I apologize for the handwaving above. (Specifically, the sentence beginning “This guarantees”.) If you’re familiar with this stuff, it will be apparent how to fill in the details. If not, trying to fill them in will only add to the pain of what’s already too long a comment :).
This is clearly much too much machinery to use here. I suspect that if we took the argument above, figured out exactly what bits of machinery it uses, and then optimized ruthlessly we might end up with a neat purelycombinatorial proof, but I regret that I am too lazy to try right now.
Rough approach for qu 6:
Join the center to each of the corners and color each segment a different color and arbitrarily coloring each ambiguous point. Radially extend the colored sections to infinity.
To prove f(x) has a fixed point consider g(x) = f(x)  x which can take values outside of the triangle. To find a fixed point, we simply need to show that g(x) will map at least one point to the center. It is easy to prove that each corner will map to the color opposite and each edge can only map to points of a different color (unless it passes through the center, in which case we would have obtained out proof). At this point the problem reduces to 5 assuming that we construct a big enough circle.
My solution for #3:
Define g:[0,1]→R by g(x)=f(x)−x. We know that g is continuous because f and the identity map both are, and by the limit laws. Applying the intermediate value theorem (problem #2) we see that there exists x∈[0,1] such that g(x)=0. But this means f(x)=x, so we are done.
Counterexample for the open interval: consider f:(0,1)→(0,1) defined by f(x)=x/2. First, we can verify that if 0<x<1 then 0<x/2<1/2<1, so f indeed maps to (0,1). To see that there is no fixed point, note that the only solution to x/2=x in R is 0, which is not in (0,1). (We can also view this graphically by plotting both y=x and y=x/2 and checking that they do not intersect in (0,1).)
EDIT: I’ve got another framing that I thought would be more useful for later problems, but I was wrong. I still think there is some value in understanding this proof as well.
In particular, look at this diagram on Wikipedia. It would be better if the whole upper triangle was blue and the whole lower triangle were red instead of just one side (you can arbitrarily decide whether to paint the rest of the diagonal blue or red). If x=0 and x=1 aren’t fixed points, then they must be blue and red respectively. If we split [0,1] into n components of size 1/n, then we can see where f(x) maps each such component to and form a line of colored points as in q1. Proving this using Sperner’s Lemma is then essentially the same as qu2.
Yeah, I did the same thing :)
Putting it right after #2 was highly suggestive—I wonder if this means there’s some very different route I would have thought of instead, absent the framing.
I’m late, but I’m quite proud of this proof for #4:
Call the large triangle a graph and the n2 triangles simply triangles. First, note that for any size, there is a graph where the top node is colored red, the remaining nodes on the right diagonal are colored green, and all nodes not on the right diagonal are colored blue. This graph meets the conditions, and has exactly one trichromatic triangle, namely the one at the top (no other triangle contains a red node). It is trivial to see that this graph can be changed into an arbitrary graph by recoloring finitely many nodes. This will affect up to six triangles; we say that a triangle has changed iff it was trichromatic before the recoloring but not after, or vice versa, and we shall show that recoloring any node leads to an even number of triangles being changed. This proves that the number of trichromatic triangles never stops being odd.
Label the three colors x,y, and z. Let v be the node being recolored, wlog from x to y. Suppose first that v has six neighbors. It is easy to see that a triangle between v and two neighbors has changed if and only if one of the neighbors has color z and the other has color x or y. Thus, we must show that the number of such triangles is even. If all neighbors have color z, or if none of them do, then no triangles have changed. If exactly one node has color z, then the two adjacent triangles have changed. Otherwise, let j and k denote two different neighbors of color z. There are two paths using only neighbors of v between j and k. Both start and end at a node of color z. By the 1D Sperner Lemma (assuming the more general result), it follows that both paths have an even number of edges between nodes of color z and {x,y}; these correspond to the triangles that have changed.
If v is a node on one of the graph’s boundaries changing color from x to y, it has exactly 4 neighbors and three adjacent triangles. The two neighbors that are also on the boundary cannot have color z, so either none, one, or both of the ones that aren’t do. If it’s none, no triangle has changed; if it’s one, the two neighboring triangles have changed; and if it’s both, then the two triangles with two nodes on the graph’s boundary have changed.
Some preliminary thoughts on q9:
As Jessicata pointed out, in 3dimensions or higher, our nhedra don’t split up as nicely as in the 2d case.
That isn’t the only issue: many of the surfaces of connected blocks may not correspond to the type of 2d grid that we just proved this result for and it doesn’t seem trivial to figure out how to characterise what kind of grids we need to extend our result too (it will be even worse in higher dimensions)
I’ve found two results: firstly that if you remove a triangular face and replace it with three others (imagine allowing the surface to jut out of the page), then the trichromatic parity will be preserved. Secondly, that we can replace two triangle with four triangles
Given what I’ve discussed above, I’d be keen for a hint as learning enough geometry to make progress on this problem would seem to be taking me pretty far afield from maths useful for airisk.
Here’s the rough idea for 5 (not a fullproof)
The bottom edge must stick in the blue and green sections meaning that if we were to divide the edge in n and see where these points map to, we would find that it would be blue or green and similarly the other edges would match the limitations in q4. If we look at the right corner, we see that the bottom edge maps to green or blue and the right edge maps to green or red, so the bottom corner must be in green. Similarly the other corners match the requirements of q4.
This lets us find a smaller trichromatic triangle. We can repeat this process an arbitrary number of times. Consider the range of possible x and y coordinates of elements in these triangles. Each time this will reduce by a particular factor, so we can see that the range of each coordinate will approach 0. I’ll leave it to the reader to show that this means that these ranges converge to a point. I’ll also leave it to the reader to show that each trichromatic subtriangle must contain the center (you may want to look up winding numbers).
I’ve realised that you’ve gotta be careful with this method because when you find a trichromatic subtriangle of the original, it won’t necessarily have the property of only having points of two colours along the edges, and so may not in fact contain a point that maps to the centre.
This isn’t a problem if we just increase the number n by which we divide the whole triangle instead of recursively dividing subtriangles. Unfortunately now we’re not reducing the range of coords where this fixed point must be, only finding a triad of arbitrarily close points that map to a triangle surrounding the centre. You can, for example, take the centre point of the first of these triangles (with some method of numbering to make the function definite) for each value of n=1,2,3.. as a sequence in R2. This must have a convergent sequence which should converge to a point that maps to the centre but I can’t prove that last stage.
Yeah, you’re right. That breaks the proof. I don’t know how to deal with it yet.
Here’s a solution to 4:
We will first prove a lemma that all connected groups of green blocks that are completely surrounded by red or blue blocks will produce an even number of trichromatic triangles. We will then augment the triangle by adding an extra blue row on the bottom and an extra red side on the right such that we now have would what be a triangle if it weren’t missing the bottom right corner. This will mean that all green blocks will now be surrounded so we’ll have an even number of trichromatic triangles, but we have added exactly one additional such triangle, so that the original has an odd number.

Proof of Lemma:
A trivial variant of 1d Sperner’s Lemma is that if we start and finish on the same colour, we get an even number of bichromatic edges. For any block that is completely surrounded by red and blue blocks, we apply this variant to show that there is an even number of bichromatic edges on the outside that then translates to an even number of trichromatic triangles.
EDIT: Actually, there is one case we can run into which is tricky and that is something like:
R R R R R
R G G G R
R G R B R
R G G G R
R R R R R R
To see how to solve this case, read how to solve tricky interior cases below.
END EDIT
Thick interior blocks work similarly, but we can run into weird scenarios such as a blue and a red surrounding by green block:
g g g
g b r g
g g g
We might also run into something like this (ie. a threespoked shape that is blue at the center and red on the sides surrounded by green).
g g g
g r g g
g b r g
g r g g
g g g
For these weird shapes we can still trace a path around this interior section, we just include going both down and up a spoke in our path (thanks Hoagy!). So the interior sections are also even.
Strategies that I’ve found helpful:
If something doesn’t seem tractable, try flipping between algebraic and geometric interpretations of a problem. Problems 1 and 3 fell to this approach.
Specific solutions (or suggestive handwaving):
Problem 1:
I thought of it like parity—going left to right, each unichromatic edge doesn’t change the color, while each bichromatic edge does. So to have an overall change, we need either 1 bichromatic edge, or 3 (1 and 2 that cancel), or 5 (1 and 4 that cancel)...
Problem 2:
I couldn’t understand this one at first. After checking Wikipedia, I think that Rn refers to the space that each point in the sequence lies within. An example of a finite sequence in R2 would then be (1,2),(3,1),(5,3)
Problem 3:
Consider the unit square. We need to draw one continuous line, going from left to right, that covers the entire vertical extent of the square. No matter how you do that, you need to cross the diagonal line from the bottom left to the top right.
Why? Because you need to touch the top and the bottom edges. You can’t do that at the bottomleft or topright corners, since then you’d touch the diagonal line. But then the point where you touch the top edge is entirely within the top triangle, and it cannot touch the bottom edge without entering the bottom triangle. Switching between triangles is identical to crossing the diagonal line.
As for why this isn’t true if the set is open rather than closed: if we exclude the edges from our consideration of “does it intersect the diagonal”, then it’s fairly trivial to construct a curve that stays inside one triangle and has a codomain of (0,1). f(x)=x2 should work.
#8 actually comes up in physics:
in the field of nonlinear dynamics (pretty picture, actual wikipedia). The fact that continuous changes in functions can lead to surprising changes in fixed points (specifically stable attractors) is pretty darn important to understanding e.g. phase transitions!
Does this work for #7? (and question) (Spoilers for #6):
I did #6 using 2D Sperner’s lemma and closedeness. Imagine the the destination points are colored [as in #5, which was a nice hint] by where they are relative to their source points—split the possible difference vectors into a colored circle as in #5 [pick the center to be a fourth color so you can notice if you ever sample a fixed point directly, but if fixed points are rare this shouldn’t matter], and take samples to make it look like 2d Sperner’s lemma, in which there must be at least one interior tricolored patch. Define a limit of zooming in that moves you towards the tricolored patch, apply closedness to say the center (fixed) point is included, much like how we were encouraged to do #2 with 1D Sperner’s lemma.
To do #7, it seems like you just need to show that there’s a continuous bijection that preserves whether a point is interior or on the edge, from any convex compact subset of R^2 to any other. And there is indeed a recipe to do this—it’s like you imagine sweeping a line across the two shapes, at rates such that they finish in equal time. Apply a 1D transformation (affine will do) at each point in time to make the two cross sections match up and there you are. This uses the property of convexity, even though it seems like you should be able to strengthen this theorem to work for simply connected compact subsets (if not—why not?).
EDIT: (It turns out that I think you can construct pathological shapes with uncountable numbers of edges for which a simple linear sweep fails no matter the angle, because you’re not allowed to sweep over an edge of one shape while sweeping over a vertex of the other. But if we allow the angle to vary slightly with parametric ‘time’, I don’t think there’s any possible counterexample, because you can always find a way to start and end at a vertex.)
Then once you’ve mapped your subset to a triangle, you use #6. But.
This doesn’t use the hint! And the hints have been so good and educational everywhere I’ve used them. So what am I missing about the hint?
An attempt at problem #1; seems like there must be a shorter proof.
The proof idea is “If I flip a light switch an even number of times, then it must be in the same state that I found it in when I’m finished switching.”
Theorem. Let G=(V,E)e a path graph on nertices with a vertex 2oloring c:V↦{0,1}uch that if deg(u)=deg(v)=1hen c(u)≠c(v)Let S:={e∈E∣es bichromatic }Then Ss odd.
Proof. By the definition of a path graph, there exists a sequence ⟨vk⟩1<k≤nndexing V(G)An edge ek={vk,vk+1}s bichromatic iff c(vk)≠c(vk+1)A subgraph Hf Gs a state iff its terminal vertices are each incident with exactly one bichromatic edge or equal to a terminal vertex of GThe color of a state is the color of its vertices. There exists a subsequence of ⟨vk⟩ontaining the least term of each state; the index of a state is equal to the index of its least term in this subsequence.
Note that none of the states with even indexes are the same color as any of the states with odd indexes; hence all of the states with even indexes are the same color, and all of the states with odd indexes are the same color.
For each state Hthere exists a subsequence of ⟨vk⟩orresponding to the vertices of Hand the least term of each subsequence is either v1r some vkhat is the greatest term in a bichromatic edge. Thus the number of states in G=1+S
By contradiction, suppose that Ss even. Then the number of states is odd, and the first and last states are the same color, so the terminal vertices of Gre the same color, contrary to our assumption that they are different colors. Thus Sust be odd.
:::
Turning each node but the last blue from left to right conserves the parity of the bichromatic edge count at each step until it is still odd at the end.
I’m stuck partway through on #4  I assume there is a way to do this without the exhaustive search I’m running into needing.
I’m going to try (nested) induction. Define triangles by side size, measured in nodes.
Induction base step: For n=2, there must be exactly one trichromatic edge.
Induction step: If there are an odd number of trichromatic edges for all triangles n=x, we must show that this implies the same for n=x+1.
We create all possible new triangles by adding x+1 nodes on one of the sides, then allow any of the previous x nodes on that side to change. Without loss of generality, assume we add x+1 edges to the bottom (nonred) side. These must be green or blue. The previous layer can now change any number of nodecolors. We now must prove this by induction on color changes of nodes in the secondtobottom layer to be red. (If they flip color otherwise, it is covered by a different base case.)
First, base step, assume no nodes change color. Because the previous triangle had an odd number of trichromatic edges, and the new edge is only green+blue, no new trichromatic edges were created.
Induction step: There is an x+1 triangle with an odd number of trichromatic vertices, and one node in the secondtobottom layer changes to red. This can only create a new tricromatic triangle in one of the six adjacent triangles. We split this into (lots of) cases, and handle them one at a time.
(Now I get into WAY too many cases. I started and did most of the edgenode case, but it’s a huge pain. Is there some other way to do this, presumably using some nifty graph theory I don’t know, or will I need to list these out? Or should I not be using the nested induction step?)
Pointers welcome!
You can use 1dSperner to deal with all the cases effectively.
Here’s a messy way that at least doesn’t need too much exhaustive search:
First let’s separate all of the red nodes into groups so that within each group you can get to any other node in that group only passing through red nodes, but not to red nodes in any other group.
Now, we trace out the paths that surround these groups—they immediately look like the paths from Question 1 so this feels like a good start. More precisely, we draw out the paths such that each vertex forms one side of a triangle that has a blue node at its opposite corner. Note that you can have multiple paths stemming from the same group if the group touches the side of the larger triangle, or if it has internal holes.
Now we have this set of paths we can split them into three kinds. The first is loops, which arise when you have a group which never touches the edge of the larger triangle, or inside ‘holes’ in large groups. These can be seen as a path starting and finishing at the same node. They therefore have an even number of bg vertices. The second kind is those that begin at the edge of the large triangle and end at the same edge. These paths begin and end on the same colour and therefore also have an even number of bg vertices. Finally and most importantly there is a kind of path that goes from one edge to the other in the case of the reds, the left edge to the right edge. This will happen once with the group that includes the top red node, and if any other group spans the larger triangle then it will generate two more of these paths. Sperner’s lemma tells us that these will have an odd number of bg vertices and we know that there will be an odd number of such paths, so this final type generates an odd number of total bg vertices.
By the way that we have defined these paths, the total number of rgb triangles is equal to the number of gb vertices on the paths in the set generated above. This number is the sum of an odd number from the spanning paths and a series of even numbers from the other paths, giving an odd overall number of rgb vertices, proving number 4 (as long as I haven’t made an error in categorizing the paths).
I hope this makes sense, let me know if it doesn’t or has errors :)
I am having trouble figuring out why #2 needs / benefits from Sperner’s Lemma.
But I keep going back to the proof that I’m comfortable with, which depends on connectedness, so I’m clearly missing an obvious alternative proof that doesn’t need topology.
I was able to get at least (I think) close to proving 2 using Sperner’s Lemma as follows:
You can map the continuous function f(x) to a path of the kind found in Question 1 of length n+1
by evaluating f(x) at x=0, x=1 and n1 equally spaced divisions between these two points and setting a node as blue if f(x) < 0 else as green.
By Sperner’s Lemma there is an odd, and therefore nonzero number of bg vertices. You can then take any bg pair of nodes as the starting points for a new path and repeat the process. After k iterations you have two values of x—only one where f(x) is below zero—that are 1/(n^k) away from each other. We thus can find arbitrarily close points that straddle zero. By taking the sequence f(x) of initial nodes x we get a sequence that, by BW, has a subsequence which converges to zero. By continuity we have proved the existence of an x such that f(x)=0.
We can be sure that the subsequence does in fact converge to zero, rather than any other value because if it converges to any number a>0, the gradient of f(x) would have to be arbitrarily high to dip back below/above 0 for a value of x arbitrarily close by and therefore would not be a continuous function.
Comments to tighten up/poke holes in the above appreciated :)
I’m having trouble understanding why we can’t just fix n=2 in your proof. Then at each iteration we bisect the interval, so we wouldn’t be using the “full power” of the 1D Sperner’s lemma (we would just be using something close to the base case).
Also if we are only given that f is continuous, does it make sense to talk about the gradient?
“I’m having trouble understanding why we can’t just fix n=2 in your proof. Then at each iteration we bisect the interval, so we wouldn’t be using the “full power” of the 1D Sperner’s lemma (we would just be using something close to the base case).”—You’re right, you can prove this without using the full power of Sperner’s lemma. I think it becomes more useful for the multidimensional case.
Yeah agreed, in fact I don’t think you even need to continually bisect, you can just increase n indefinitely. Iterating becomes more dangerous as you move to higher dimensions because an n dimensional simplex with n+1 colours that has been coloured according to analogous rules doesn’t necessarily contain the point that maps to zero.
On the second point, yes I’d been assuming that a bounded function had a bounded gradient, which certainly isn’t true for say sin(x^2), the final step needs more work, I like the way you did it in the proof below.
I hit that stumbling block as well. I handwaved it by saying “continue iterating until you have x(k,B) and x(k,G) such that f(xk,B)<0, f(xk,G)≥0, and f has no local maxima or local minima on the open interval (xk,B,xk,G)”, but that doesn’t work for the Weierstrass function, which will (I believe) never meet that criterion.
Here is my attempt, based on Hoagy’s proof.
Let n≥1 be an integer. We are given that f(0/n)=f(0)≤0 and f(n/n)=f(1)≥0. Now consider the points 0/n,1/n,…,(n−1)/n,n/n in the interval [0,1]. By 1D Sperner’s lemma, there are an odd number of j∈{0,…,n} such that f(j/n)≥0 and f((j−1)/n)≤0 (i.e. an odd number of “segments” that begin below zero and end up above zero). In particular, 0 is an even number, so there must be at least one such number j. Choose the smallest and call this number jn.
Now consider the sequence (jn/n)∞n=1. Since this sequence takes values in [0,1], it is bounded, and by the Bolzano–Weierstrass theorem there must be some subsequence (kn/n)∞n=1 that converges to some number x∈[0,1].
Consider the sequences (f((kn−1)/n))∞n=1 and (f(kn/n))∞n=1. We have f((kn−1)/n)≤0≤f(kn/n) for each n≥1. By the limit laws, (kn−1)/n→x as n→∞. Since f is continuous, we have f((kn−1)/n)→f(x) and f(kn/n)→f(x) as n→∞. Thus f(x)≤0 and f(x)≥0, showing that f(x)=0, as desired.
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 BolzanoWeierstrass 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.
Ex 5 (fixed version)
Let D denote the triangle. For each n∈N, construct a 2d simplex Sn with (n+1)2 nodes in D, where the color of a point corresponds to the place in the disk that f carries that point to, then choose xn to be a point within a trichromatic triangle in the graph. Then (xn)n∈N is a bounded sequence having a limit point x∗. Let t be the center of the disc; suppose that f(x∗)≠t. Then there is at least one region of the disc that f(x∗) doesn’t touch. Let ϵ be the distance to the furthest side, that is, let ϵ=max{d(f(x∗),G),d(f(x∗),R),d(f(x∗),B)}. Since the sides are closed regions, we have ϵ>0. Using continuity of f, choose δ∈R+ small enough such that Bd(x∗,δ)⊂Bd(f(x∗),ϵ). Then choose n∈N large enough so that (1) all triangles in Sn have diameter less than δ2 and (2) d(xn,x∗)<δ2. Then, given any other point y in the triangle around xn in Sn, we have that d(y,x∗)≤d(y,xn)+d(xn,x∗)<δ2+δ2=δ, so that d(f(y),f(x∗))<ϵ. This proves that the triangle in Sn does not map points to all three sides of the disc, contradicting the fact that it is trichromatic.
Ex 6
(This is way easier to demonstrate in a picture in a way that leaves no doubt that it works than it is to write down, but I tried to do it anyway considering that to be part of the difficulty.)
(Assume the triangle T=¯¯¯¯¯¯¯¯¯¯¯¯ABO is equilateral.) Imbed T into R2 such that O=(0,0), A=(−12,12√3), B=(12,12√3). Let f:T↦T be continuous. Then h:T↦R2 given by h:x↦f(x)−x is also continuous. If h(x)=O=(0,0) then (0,0)=h(x)=f(x)−x⟹f(x)=x. Let R be the circle with radius 2 around O; then h(T)⊂R because h(x)=f(x)−x≤f(x)+x≤2 (it is in fact contained in the circle with radius 1, but the size of the circle is inconsequential). We will use exercise 5 to show that h maps a point to the center, which is O, from which the desired result follows. For this, we shall show that it has the needed properties, with the modification that points on any side may map precisely into the center. It’s obvious that weakening the requirement in this way preserves the result.
Rotate the disk so that the red shape is on top. In polar coordinates, the green area now contains all points with angles between 60∘ and 180∘ , the blue area contains those between 180∘ and 300∘, and the red area those between 0∘ and 60∘ and those between 300∘ and 360∘. We will show that h(¯¯¯¯¯¯¯¯AB) does not intersect the red area, except at the origin. First, note that we have
h(¯¯¯¯¯¯¯¯AB)={f(x)−xx∈¯¯¯¯¯¯¯¯AB}⊂{y−xx∈¯¯¯¯¯¯¯¯AB,y∈T}={T−xx∈¯¯¯¯¯¯¯¯AB}=T−¯¯¯¯¯¯¯¯AB
Since both T and ¯¯¯¯¯¯¯¯AB are convex combinations of finitely many points, it suffices to check all combinations that result by taking a corner from each. This means we need to check the points
A−A and B−A and C−A and A−B and B−B and C−B.
Which are easily computed to be
(0,0) and (−1,0) and (12,−12√3) and (1,0) and (0,0) and (−12,−12√3)
Two of those are precisely the origin, the other four have angles 270∘ and 150∘ and 90∘ and 210∘. Indeed, they are all between 60∘ and 300∘.
Now one needs to do the same for the sets T−¯¯¯¯¯¯¯¯OA and T−¯¯¯¯¯¯¯¯BO, but it goes through analogously.