Fun Fact - The Hadwiger Nelson Problem

You know what's cool about mathematics? We can pose a problem that a junior high student can understand, yet nobody knows the answer. Here is an example. It is called the Hadwiger Nelson problem, after its creators. How many colors are needed to color all the points of the xy plane, so that no two points, 1 unit apart, have the same color?

Two won't do, as shown by an equilateral triangle in the plane, 1 unit on a side. Each corner is a distance of 1 from the other 2, hence you need at least 3 colors.

Three colors won't do, as per the following argument. Pain the origin red, and designate 2 points orange and yellow on the unit circle, forming an equilateral triangle. Draw a bisector through this triangle out to a radius of sqrt(3). That point produces another equilateral triangle with orange and yellow, and it too must be red. Every point on the circle of radius sqrt(3) is red, and that is impossible, as shown by any two points on that circle that are 1 unit apart.

If you extend this problem to higher dimensions, coloring all the points in n-space, then the above construction, i.e. painting the origin and the entire hypersphere of radius sqrt(3) red, shows n+1 colors are not sufficient.

If you tile the plane with well-defined regions, like coloring in a coloring book, then the minimum is 6. We don't know if there is a 6 color solution, but there is a 7 color solution, which I will describe below. Four or five color solutions might exist if the plane is fuzzy, i.e. just a smear of different colors no matter how powerful your microscope.

7 Colors

The base cell is a regular hexagon, ½ inch on a side. (Make it just a hair less than ½ if you want some wiggle room.) The diameter of this hexagon, from one corner to the opposite corner, is 1, hence it can be colored with one color. Tile the entire plane with these hexagons. Hexagons point up and down. As we move along one row of hexagons, color the cells red orange yellow green blue indigo violet, and repeat. The row just above this one is colored the same way, but shifted ober, so that the red hexagon rests above yellow and green. The row above this is colored the same way, with the same phase shift. This pattern repeats as successive rows tile the entire plane. Verify that the closest red hexagons are sqrt(7)/2 = 1.32 inches apart. Therefore points that are 1 unit apart always have different colors.

The 7 color hexagon tiling is regional, i.e. small regions of the plane are assigned individual colors and it all works out. Any regional solution requires at least 6 colors. Let's see if we can prove that, and in the process, put some constraints on a 6 color solution.

Definitions

A region is an open connected set, and its border is, well, its boundary. Borders are piecewise smooth, so that they almost look straight at a microscopic scale. Each region is assigned one color, and each border point has a color that matches one of its adjacent regions. We'll see that the borders are not important; if we can make the regions work, we can make the borders work.

The diameter of a region cannot exceed 1, else 2 points somewhere along the path from one end to the other would have the same color and be 1 distance apart. Show this by the intermediate value theorem, as the distance ranges from 0 to something greater than 1. Thus regions can only be so big. We saw this with our hexagons. I chose hexagons with a diameter of 1, or something slightly less than 1, so that borders are not an issue.

Suppose a border between red and yellow bends at a point p. (Remember, the border only has to be piecewise smooth.) We are small, so the border is linear, looking like to segments that meet at p at some angle, such as 170 degrees. The yellow side is 170, the red side is 190. Draw an arc with curvature 1 connecting the 2 segments on the yellow side, thus smoothing out the bend. Everything between the arc and the angle can be painted red. If q is such a point, and if q is 1 point away from a point r, then a circle centered at r already intersects the red region, so r could not be red. No trouble painting q red. Leave the arc, the new border, yellow if you like, it was yellow before, or make it black because borders don't matter. After this transformation, all borders are smooth.

In the same way, a border with curvature greater than 1 can be smoothed out to curvature 1. There is no need to turn faster than the unit circle.

A point p is a vertex if at least 3 regions meet at p.

Suppose two red regions meet at a vertex p, showing an angle of less than 180 degrees. Put p at the origin, and let red lines meet at p, with the y axis as their bisector. The story is almost the same as that shown above. Draw an arc through the yellow region just above p, and paint everything strictly between this arc and the red regions red. The only trouble might be the pesky point p, which gives us a means of escape. In other words, q, trapped below the arc, could be one point away from a red point r, with the circle c centered at r passing through q and p. However, if r is red then it is part of a red region. A red disk contains r, and those points collide with the red points near p. this is a contradiction. Each q between the red regions and the arc can be painted red, and the two red regions merge into one. Assume this has been done wherever possible. Therefore, if two red regions meet at p, they present angles of 180 degrees on either side. The regions come to infinitely sharp points at p, and are called needles. A region at a vertex is normal if its angle is greater than 0 degrees, or a needle if its angle is 0 degrees.

Three red regions cannot meet at p, thus every vertex has finitely many incident regions. You can count them off in a counterclockwise direction.

Borders

We can leave the borders black, because any regional solution extends to the borders. If p is on the border, give it the color of the region directly to its right. If a border, i.e. a line segment, enters p from the right then assign it the color of the region just above this line. Assume p is colored red, and suppose r is 1 unit away and belongs to a red region. Since r is in the interior of a red set, some disk about p is not red, and p would not be colored red. Suppose r is on a border and it too is colored red. Red points approach r from the right, or from the right and just a hair above. With these in place, red cannot approach p from the right. This is a contradiction. the border has now been colored consistent with the regions. Thus we can simply color the regions, i.e. the open sets.

Needles

Let p be a vertex with a red needle pointing up from below. This needle curves away from p, to the left or the right, or both if the left side curves left and the right side curves right. If both sides curve right then reflect the picture. Now we know the left side curves left, with curvature at most 1. The border of this needle may trace a circle of radius 1, or it may be a little straighter than such a circle. If the right side also curves left its curvature is less than 1, or becomes less than 1 as soon as it leaves p. It is straighter then a circle of radius 1.

Let c be the unit circle about p. The area just inside the top half of c can't be red, and the area just outside the bottom half of c can't be red. Let q be 1 unit to the left of p and let r be 1 unit to the right of p. These are transition points. The points along the qr line, just inside c, arbitrarily close to q and r, can't be red. This is obvious near r, but takes a bit of thought near q. A point just to the right of q is the center of a unit circle d that just misses p. This circle curves faster than the right side of the needle, so even if that edge curves left, d crashes into it. Thus the points just to the right of q cannot be red. By a continuity argument, or more brute force geometry, the area just inside c, near the points q and r, can't be red. This non red area straddles c below, then moves up along the inside of c, crawling across q or r. Put this altogether and a continuous band of nonzero thickness runs along c, inside above, outside below, and inside near q and r, and this band cannot be red.

If there are 2 red needles above and below, then reflect this band vertically and paste it on top of the original. Now a continuous non red band of nonzero thickness runs along c, inside and outside of c all the way around, except for the qr line where the band is inside only. Red can only approach c at q and r from outside.

Return to 1 red needle from below, with its corresponding non red band inside c above, straddling c just below q and r, and then outside c below. Suppose red does not approach r from the right. There is a small disk about r that is not red. It is possible to paste a tiny red triangle onto the right side of the needle pointing up at p, thus creating a normal red region at p. The triangle may have to be very small, and highly acute, if the non red disk about r is small. Apply the same reasoning that we've used before. Is there a point in this triangle that can't be red, because there is another red point one unit away? Let k be a point in this triangle and imagine a unit circle d passing through k. If d intersects the needle then its center cannot be red. Thus d is nearly vertical through k, and its center is near q or near r. Points near r are not red, so d curves left. Its center is near q, but still to the right of q, and that can't be red either. In other words, d curves faster than the right side of the needle, and crashes into the red needle. There is no trouble coloring this triangle red, along with the gap between the needle and the triangle, if both edges of the needle curve left and there is such a gap. Similar comments apply if red does not approach q from the left.

Assume we have thickened needles into normal regions wherever possible. If a red needle persists then red approaches both q and r from the left and right respectively. These red regions could head straight up from q and r, but they can't lean in at a proper angle, because that would cut into c, and the band just inside c, above q and r, cannot be red. By the same reasoning, they can't lean in towards c as they travel down from q and r. Even moreso, since the band outside of c, below q and r, cannot be red.

If the red needle curves left with curvature 1, then the red region at q cannot descend straight down. If we head straight down from q, and curve left with maximum curvature 1, in parallel with the needle at p, then red points will be 1 unit apart. The angle is away from vertical whenever the red needle has curvature 1.

Similar exclusion bands can be drawn for a normal region at p. If the angle is 20 degrees, symmetric about the y axis, then the transition points q and r climb 10 degrees up the unit circle c. A continuous non red band runs around c, inside from r to q above, outside from q to r below, and inside near the points q and r.

Turn the entire picture 10 degrees clockwise for convenience. This puts r back on the x axis. The red region runs straight down vertically from the origin. Assume it does not curve left with curvature 1. (This was the case when the region was a needle.) Further assume red does not approach r from the right. We can paste a small acute triangle to the right of the red region at the origin. The reasoning is the same as that shown above. The region has been "thickened".

2 Color Trouble

Suppose an inside area of c, stretching more than 120 degrees, is restricted to orange and pink. Start at one end and assume the color touching c is orange. Let y be the point along c where you first encounter pink. Let z be 60 degrees over from y. Draw the arc through z centered at y. Points inside this arc are pink and points outside this arc are orange. In the same way, draw an arc through y centered at z. Points inside this arc are pink and points outside this arc are orange. The 2 arcs bend towards each other, and that brings orange points within 1 of each other. This 2 color arc cannot exist.

The same thing happens in a pink orange area running along the outside of c, although in this case even 120 degrees is trouble. Define y and z as above, and the same problem occurs, unless y is at 60 degrees and z is at 120 degrees. In this case points just above y are in range of orange and pink, and that is a contradiction. 2 colors along exactly 120 degrees on the inside is no trouble though, as shown by 6 pieces of pie having 6 colors around.

This result disappears if choke points are strategically placed. Draw a 60 degree orange region straddling c, somewhat like a football, then a 60 degree pink region, then a 60 degree orange region. That's 180 degrees of orange and pink. The 2 points demarking pink are choke points. The orange pink restriction does not apply at these two points. If it did, there would be 2 color trouble. We can even have 6 regions orange pink orange pink orange pink running all the way around, with 6 choke points forming a hexagon. This is an anomaly; 2 color annuluses are usually impossible.

Sometimes the arc is less than 120 degrees, yet we can still find trouble. Let y and z, in the interior of the arc, (i.e. not the end points), be 60 degrees apart, with pink approaching y and z from within. That means orange approaches y and z from without. Draw the circular pink orange borders as before, and orange points will be within 1 of each other. There could be choke points along the way, as long as they aren't y and z. In fact we only need tiny (arbitrarily small) pink orange 2 color bands at y and z. If the regions are both inside c or both outside c, the borders pull the orange regions too close together. If one region is inside c and one outside c, the borders pull the pink regions too far apart.

2 Color Thickening

Consider a 2 color arc, inside or out, > 60 and ≤ 120. There are no choke points. It is orange at the right, and 60 degrees over it has to be pink. Pink could start earlier but it must be extant at 60. Slide both points counterclockwise t degrees until there is a color change. Pink becomes orange and orange becomes pink. These are points y and z, still 60 degrees apart, and they produce the trouble described in the previous paragraph. Thus this color change cannot occur. It's pink all the way to the other end of the 2 color band. If the arc length is 70 degrees, then 10 degrees on one end is orange and 10 degrees on the other end is pink. We don't know what happens in the middle - could be a series of pink and orange stripes.

The right is not just orange along c and pink a little bit away from c, for that would still be in range of pink on the left. No, it's solid orange on the right and solid pink on the left, for t-60 degrees.

2 Color Annulus

As you travel around c, assume a series of inside and outside bands bordering c, or straddling c, are restricted to orange and pink. c has finitely many choke points, where the 2 color constraint does not apply. At least one band runs inside of c, or outside of c, for more than 60 degrees, with no choke points. Finally there is a convexity requirement, which is not hard to meet in practice. If a point is in such a band, all the points between that point and c are in the band. Move toward c, and you are still restricted to orange and pink. Such an annulus cannot be colored.

Suppose pink and orange regions run along c within the 2 color bands. Let s be our start point, at the beginning of the +60 degree continuous band if that band is inside c, or at the end of that band if the band is outside of c. Let s seed a hexagon around c. Rotate it if need be, to avoid the choke points of c. Adjust the hexagon again, so none of its points are on a pink orange border. Now we're ready to start.

assume, without loss of generality, that the band containing s is inside c, and the region containing s is orange. When I say "containing s", I mean containing points inside c and arbitrarily close to s.

The band from s to s+60.1 degrees has a certain thickness inside c, and is continuous on a compact space, thus it attains its minimum. Call this thickness t. You can think of the band as a strip of width t if you like.

We have pink at t+60, and that means we have orange at s starting at c and extending through the thickness t. We don't have a tiny orange bubble surrounded by pink. In fact the orange region fills the band until it changes to pink, somewhere between s and s+60.

Move s a hair inside c, and move the other 5 points of the hexagon inside or outside of c, staying within their bands, and jiggle them just a bit so that each is 1 unit ahead of the previous. Take one more step, and the seventh point doesn't land on s any more, but by keeping the points of the hexagon close to c, it can land arbitrarily close to s. These points are orange pink orange pink orange pink and finally orange again, in the same region as s. Move the inside points farther in than the outside points move out, so that s7 lands just a hair ahead of s1. We have made progress.

Take another 6 steps and make more progress. Each cycle, comprising 6 steps, advances the point in the orange region counterclockwise along c. This progress need not shrink to 0, in zeno's paradox, because the orange region has a thickness t. We can always keep the sixth point a tiny bit away from c, and advance by some angle δ. So we step, slowly but surely, towards the orange pink border.

Finally, take another 6 steps and land in the pink region next to the orange region. However, this point must still be orange. This is a contradiction, hence the pink orange coloring cannot exist.

I'm glossing over something here; what if there is no "next" pink region? What if infinitely many pink and orange stripes shrink to infinitely thin regions, as they approach the end of the orange region? Then there is no next region. There are other reasons these stripes cannot exist, but even if they did, you could step through just the right angle, to land inside a pink stripe, and obtain the same contradiction.

No Adjacent Needles

Imagine a blue needle sliding along side a red needle. The entire band along c that is not red is not blue. And with green on the left of these needles, and yellow on the right, we have a band that is not red blue green or yellow. The only choke points are q and r. Even if we allow 6 colors, this leaves a 2 color annulus, and that is impossible, as shown by the previous theorem. Two needles, red and blue in our example, cannot exist next to each other. Nor can one needle exist in a 5 color solution.

You don't need the annulus theorem for this; the top half of c presents a continuous 180 degree 2 color arc, and that is 2 color trouble.

Lopsided

Suppose two colors consume 60 degrees or less. This is called lopsided. Let a circle just miss p and cut through these 2 colors and the colors on either side. this circle pivots about p, 60 degrees one way and 60 degrees the other. This defines a 2 color region outside of c with arc at least 120 degrees. That is impossible, hence we can rule out any lopsided arrangements.

If 3 colors consume less than 120 degrees that is also lopsided. An inside region, or outside region, as you prefer, of more than 60 degrees, is 1 color, and that can't happen.

Finally, 4 colors consuming less than 180 degrees is lopsided. A circle cuts through them, and the other 2 colors, and the center of said circle exhibits the seventh color. This could happen without the previous 2 conditions; if each region is 44 degrees then each pair of regions is 88 and 3 in a row are 132.

p could be lopsided when 4 regions consume exactly 180 degrees, if both borders are straight lines, or curve toward the other 2 regions with curvature less than 1. Example: straight lines and angles of 45 45 45 45 90 90. A circle just grazes p, parallel to the straight line, and cuts all 6 regions. This doesn't happen very often.

The lopsided criteria ratchet back if we only allow 5 colors. No region 60 degrees or less, no two adjacent regions < 120, and no 3 regions < 180.

No 4 Color Solution

With just 4 colors, no region can be less than 120 degrees, else the arrangement is lopsided. At least 3 regions meet at a vertex, hence every vertex joins 3 regions, each 120 degrees. These are called steiner points.

Let p be a vertex joining red, yellow, and green. Other than 6 choke points, a band around c is entirely blue. This is impossible.

No 5 Color Solution

If 3 meet at a vertex we have a 2 color annulus, which doesn't work, unless the choke points form a perfect hexagon. That could happen if the 3 regions are each 120 degrees. Thus every 3 region vertex is steiner.

Let p be a steiner vertex, with the red yellow border heading off to the right of p. Suppose this border has no curvature, a straight line. There should be a choke point z, at the top of c, straight up from p, but watch what happens. A circle d has its center just below z. It grazes p, and because the border to the right of p is straight, it cuts through all three regions. The area just below z is not red yellow or green, and z is not a choke point. It is a transition point, but not a choke point. The 2 color band runs along the inside of c, up to and just past z; and starting at z the band runs along the outside of c. Yes, z could be a choke point, if the red yellow border curves upward with curvature 1, but then the point 1 unit below p, at the bottom of c, is not a choke point. We can't have a perfect hexagon of choke points, thus the 2 color annulus cannot exist. Hereinafter, 4 or 5 points meet at each vertex.

Put 4 regions at p, each region more than 60 degrees to avoid lopsided. Suppose regions run red yellow blue green counterclockwise around p, with red at the bottom. Orange is the fifth color. Arrange things so that red + blue is no more than 180. both are greater than 60, so both are less than 120. Let the angles be s t u v around, with s and u strictly between 60 and 120. Look at the arc of c above p. Outside is orange or red for 180-u degrees. Inside is orange or blue for 180-s degrees. It's a bit of work to demonstrate the overlap.

Center red about the y axis. Angles are measured from the positive x axis counterclockwise in the usual manner. The inner band runs from ½s to 180-½s. The outer band runs from ½s + t + u - 180 to ½s + t. tilt your head and subtract ½s. The inner band runs from 0 to 180-s. The outer band runs from t + u - 180 to t. Assume, without loss of generality, u ≥ s. If u+t and u+v are both < 180 then 2u+t+v < 360, whence s+t+u+v < 360, which is impossible. Reflect if need be, so that u+t is at least 180. Now t+u-180 is at least 0. The overlap runs from t+u-180 to 180-s, or t, whichever is shorter. t - (t+u-180) is 180-u, which is greater than 60. Or, (180-s) - (t+u-180) = 360-(s+t+u) = v. Remember that v > 60. Either way we have an overlap of more than 60 degrees. 2 color thickening applies.

Start at the right and proceed counterclockwise until the color changes. If we start with red and blue, and one changes to orange before the other, or they both change at the same time, we have a vertex with 3 colors, which is impossible. thus one or both regions starts out orange. Start with double orange. If inside becomes blue and outside becomes red at the same time, we have a vertex with 3 colors. One of them changes before the other. Suppose inside changes to blue first; outside is still orange. Orange inside can't come in at an angle, it has to look like a needle running along c, but its curvature, bent inward by c, is greater than 1, so that is impossible. So outside changes to red first. It has to change back to orange, and we're back to double orange. Eventually orange inside changes to blue, a contradiction. Next start with red outside and orange inside. Orange can't change to blue, or we have a 3 color vertex. Red changes to orange, which is double orange, which we already covered. Finally start with orange outside and blue inside. Blue gives way to orange, and we have the same orange curvature problem we saw before. Therefore 4 colors do not meet at p.

The last case is all 5 colors at p. Let them run red yellow blue orange green around. If red + yellow is 140 degrees (to illustrate), then a 40 degree arc of c is orange inside and red or yellow outside. Can't be both red and yellow, else we have a 3 region vertex, so pick one, say yellow. Tick around c counterclockwise and color the next adjacent arc. If orange + green is 150 degrees (to illustrate), then a 30 degree arc of c is yellow outside and orange or green inside. 40 + 30 is 70, which is the angle of blue, which is guaranteed to be more than 60. Yellow points are 1 unit apart. That's the last case; there is no 5 color regional solution.

I work on this problem from time to time, looking for a 6 color regional solution or trying to disprove. I have ruled out a few cases here and there, like red and blue needles pointing at each other, but I'm not sure this brute force approach will produce an answer. if you wish.

Each Needle has Curvature 1

Let a red needle point up at p, with green to the left and yellow to the right. We don't know if green and yellow are a fraction of a degree, or 180 degrees. It is the edges of green and yellow, along side red, that are important in the following analysis.

The aforementioned band, inside the top half of c and outside the bottom half of c, cannot be red green or yellow. The thickness of the band will depend on the size and shape of the red green and yellow regions.

Look directly to the right of q along the qr line, or even at a downward angle. We are of course staying arbitrarily close to q. This area can't be red or yellow, but it could be green, only if the red needle curves left in a perfect circular arc of curvature 1, whence green, next to the red needle, is never 1 unit away from points near q. If the red needle has curvature less than 1, then this area near q can't be green either. Similarly, a green border could descend directly down from q, but only if it curves right with curvature 1.

One could imagine green descending down from r; its curvature to the left is at most ½, determined by the green region at p, and that runs outside of c. So the band is non green just outside of c and below r. this completes the band around c, non green inside above and non green outside below. There is also a non green region to the left of r, and maybe to the right of q if the needle has curvature less than 1.

Earlier we tried to thicken the red needle; now let's try to paint its tip green. Place k near the tip, close to p, and suppose z is a green point 1 unit away. z is the center of a unit circle d that passes through k. With the green wall to the left, d is near vertical at k, and z is a hair to the right of q or the left of r. We already said there is a nongreen area to the left of r. On the other side, if green does not approach q from the right, then we can recolor the tip green and remove the needle. This is assured when the curvature of the needle is less than 1. Assume this has been done whenever it can be done. Now a needle persists iff if has curvature equal to 1, left and right, and green and yellow regions approach q and r from inside, and red regions point in towards q and r from outside, as per an earlier result. Since the needle has curvature 1, the red regions at q and r do not descend straight down, as shown earlier. There is a gap below q, between green and red, that must be filled with other colors. In other words, q and r are vertices.

The green at q is not a vertical needle pointing up at q, as its left edge curves 1 to the right, and its right edge curves faster than 1. If it runs vertically down at q it is anormal region down and to the right of q. It could be a needle poking in from the right however, or even a normal region entirely above the x axis. It can't run straight up from q however, as that would be in range of the green region just to the left of the red needle at p. Green stays to the right of the vertical line passing through q. In the same way, if the green border runs down from q, it can't extend straight up at p.

Something fills in between green and red below q - at least one normal region and perhaps another needle. What color is the region just below q? Let r1 be the region below q and to the left of c, and let r2 be below q and to the right of c. They may of course be part of the same region. If r1 is different from r2, if there is in fact a border between them, r2 could be green, the green up against q, or r2 could be some other color, with green higher up. r1 is not red of course, and not yellow, as that is within range of yellow to the right of the red needle. And not green, or any color that approaches p from the left. If r2 is not green, it is not yello and not red, and not any color that approaches p from the right, or directly above, e.g. a needle pointing down to p, or a region to the left of p whose border runs straight up from p. If r1 and r2 are one combined region, then it is not any color that approaches p.

3 Color Blend

Let a pink freen band run from r along the top of c, merging into a pink yellow band running around to q. These bands could be inside or outside. They overlap at or near the top of c. Thus pink is at the top. Neither band can be more than 120 degrees by 2 color trouble. Each band is 120 or less, and since there is overlap, each band is more than 60. By 2 color thickening, each band is solid pink starting at 60 degrees up, and solid yellow or green near q and r respectively. Pink is at most 60 degrees, and can't be more, so it is 60. Green and yellow fill in, and they too must be 60. This is impossible outside of c, i.e. the green pink band is 120 degrees. It could happen inside of c if the bands are prescribed just so, i.e. 60 60 60.

Next assume there is no overlap, the bands meet at a choke point z at or near the top of c, wherein points near z could be pink green or yellow. Assume each band is greater than 60, so thickening applies. If pink is at the top of both bands, it is 60 across, leaving green and yellow 60 as before. This can only happen inside c, and points near z fill in with pink as before.

Put pink at r and yellow at q, so that pink and green meet at z. If yellow does not approach z, then it's all green or pink at z, and another color change from green to pink at z - 60 degrees, and that is 2 color trouble. So yellow approaches z. We can't run pink green yellow green at z, so it's pink yellow green pivoting around z. Let y = z + 60 degrees around. This is a change from pink to yellow. Yellow points are pulled towards each other near y and z, and that is a contradiction.

Put pink at q and r, so that green and yellow meet at z. If pink approaches z, then combine this with the pink green change at z-60, and pink points are pulled toward each other near y and z. Thus we have a green yellow change at z. This is possible, if regions run pink green yellow pink around, and each is 45 degrees, for example.

2 Red Needles

If two red needles point at each other, we will show that one side is one color (180 degrees) and the other side is another color. No other configuration can exist.

Red does not run straight down at q, nor does it run straight up. Red comes to a point at q from the left, and red comes to a point at r from the right. Without these side regions, we would thicken one or both needles and merge the 2 red regions into one. q and r are vertices joining red regions with other regions around.

Suppose a blue needle points at p and makes an angle of less than 120 degrees with the red needle. With the color between, this is lopsided. There is no room for a blue needle anywhere. All other regions are normal.

A needle cannot be next to a region of 60 degrees or less, as that would be lopsided. If 2 red needles have green and blue on the left side of p, green and blue are both more than 60 degrees, and of course less than 120.

If 2 red needles have yellow blue orange on the right, in that order, yellow cannot be 60 or less, as that forces a lopsided configuration. That leaves blue orange red less than 120, which is lopsided.

If yellow blue orange pink are on the right then red yellow blue orange are less than 180, which is lopsided. Each side has 1 or 2 colors.

If green is on the left then we have yellow or yellow blue on the right. Consider the second case. Ignore the needles for the moment and consider any 3 colors that meet at a point p. Borders may curve, but at a microscopic level they appear straight, so it looks like three line segments meet at p, separating three regions that are green yellow and blue. If z is a point on c, draw the circle about z, which necessarily passes through p. If this circle is tangent to one of our three lines then z is a transition point, and could be a choke point. Thus I am omitting 6 points from c. Let z be any point on c, aside from the aforementioned 6 points, and draw a circle about z, which necessarily passes through p. At least 2 of the 3 lines will be on one side of this z centered circle or the other. Slide z and its circle directly towards or away from p, so that the circle passes through all 3 regions. For example, if 2 of the borders are inside this circle, closer to z, then z demarks a band that travels along the outside of c. Points in this band, just beyond z, are 1 unit away from all three regions at p, and cannot be green yellow or blue. Nor can they be red, once you bring the red needles back in. At the same time, if y is on c and diametrically opposite to z, then y demarks a band that travels along the inside of c. Points in this band, just inside of y, are 1 unit away from all three regions at p, and cannot be green yellow or blue, nor red. We have built a 2 color annulus, and that is impossible.

Place green and blue on the left, and yellow and orange on the right. Pink is the leftover color. Assume blue + orange consumes less than 180 degrees. This produces the 3 color blend contradiction described in the previous section. If the angle is greater than 180 we find the same contradiction using the needle below. Therefore blue + orange = 180, and p looks like vertical angles.

3 color Blend places pink regions outside of c, just above q and r. If they are needles, they point straight down. However, pink does not approach p, so such a needle would be thickened to a normal region. by symmetry, a normal pink region approaches r from below. These regions merge together, and they push red away from r at the right, or they push orange away from r at the left. This allows us to thicken the red needle pointing down at p, or recolor its tip. This is a contradiction, so blue + orange = 180 doesn't work either. That completes the case of red needles and 2 colors on either side. The only case left is the aforementioned green on the left and yellow on the right.

Red Blue Needles Up and Down

Let a red needle point up at p, and let a blue needle point down at p, with 180 degrees of green on the left. Green cannot be vertical at q; it comes to a point. Remember that red does not descend vertically down from q, nor blue vertically up from q. In the extreme they could switch, with red vertically up from q and blue vertically down. The normal region that fills in the gap below q, to the left of green, cannot be green, or red, or blue, or any color that approaches p from the right. If there are three colors to the right of p then we have run out of colors. If there are 2 colors, say yellow and orange, then we are left with pink. Yet it is pink above q and pink below q, forming an angle around green, and these 2 regions would merge, and push green away from q, whence the red and blue needles would have been modified earlier. hence there is only one color, say yellow, to the right. That leaves pink and orange below and above q. By symmetry we have pink and orange at r.

Let's explore this for a bit. place y and z on c, at 60 and 120 degrees respectively. Let d be the unit circle centered at q, so that z is on c and d. Let e be the unit circle centered at r, so that y is on c and e. Looking above the x axis, a band above c is not blue green or yellow. A band below c is not red green or yellow. There are 4 regions at z, defined by c and d. We'll start with the region above z. There is a comparable region above y, and if each region is filled in with one color, it can't be the same color. In fact none of the regions around y can match the color of the region above z, or the region below z.

Remember that pink and orange fill in all the way to the vertical line at q. The sequence is pink green orange, and nobody else. Let's put pink on top, thus a band above d is not pink. Points above z are orange or red. Let l be the line passing through q, parallel to the line tangent to d at z. Suppose orange is also above l. Perhaps green is thin at q, sandwiched between pink and orange. Now the band above d is not orange, and the entire region above z is red. The region to the right of z is blue. The regions above and below y are not red or blue. At best, one is pink and the other is orange. Thus the region below z is not pink or orange. With blue and red regions at z, outside of d, the red and blue regions at q, (which must exist), are pushed below l. Thus the region below z is not blue or red. We're out of colors. Therefore orange stays nicely below l, and pink stays above a corresponding line with positive slope. Green has an angle greater than 60 at q.

With pink and orange behaving, the region to the right of z is blue and/or orange. If there is any blue, that pushes the blue region at q below l, whence the region below z is pink. Nothing around y is pink. Depending on the placement of orange at r, the region above y is red, or the region below y is blue. The latter collides with the region to the right of z, hence orange is above r, the region above y is red, and the region below y is orange. The region above z is red or orange, and that doesn't work. Therefore there is no blue to the right of z; that region is orange.

Suppose pink is above r. By symmetry, there is no blue to the left of y; that region is orange. With these orange regions in play, the only color left for the region above z, and the region above y, is red. This puts red points 1 unit apart. Therefore pink is below r and orange is above r.

As before, there is no blue to the left of y; that region is pink. The region above y is red. This pushes the red region at r down, so that the region to the right of y is not red. There are no colors left for this region. That completes the case of green and yellow bracketing red and blue needles.

The last case puts two colors on one side and two on the other, all 6 colors at p. By 3 color blend, the 2 colors on either side of each needle consume 180 degrees, thus forming vertical angles with the needles. Starting with the redneedle pointing up, and running counterclockwise, the colors run red yellow pink blue orange green. Assume the transverse line does not curve up with curvature 1. In other words, the yellow pink border does not curve up with curvature 1, or the orange green border does not curve up with curvature 1. Apply 3 color blend to the inside band of the top half of c. Because the curvatures are not 1, the two 2 color bands have a tiny overlap. Starting at r and running around to q, regions run pink, blue, and orange, and each is 60 degrees. Now apply 3 color blend to the outside of the botom half of c. We have to put pink at r, but we can't, because there is already 60 degrees of pink at r. That's the last case, hence two needles of different colors never point directly at each other.

Further Reading

The Hadwiger Nelson problem.