Hacker News Reader

Comment by Phemist | Hacker News Reader

I have always wondered about this sample. Consider the possible 4-colours to be red, blue, green and orange, as in the image. We need to determine the colour of the black square. All 4 colours are joined in this inverted cross like formation and the center of the cross (a gray pixel atm) kind of indicates an infinity point. If the space in which these colours are drawn is not discrete, then they can all be said to join at the center of the cross.

Is this sample just not allowed by the rules of the "game"?

Consider it an extreme case of gerry-mandering...

View on HN

Your example adds more constraints than the original problem, by pre-assigning colors to regions and then asking how to solve for the black region.

In the original problem statement, you could solve by re-assigning your green region to be orange, your red region to be blue, your black region to green, and the white regions to red. Also note that regions that meet at a single point (as in your example) are not considered to be adjacent.

aha, so infinities are not allowed. Fair enough, in that case the gray pixel needs to be filled with one of the colours and the two colours connected to that specific one become interchangeable.

so in essence there is an additional constraint, that each touching edge has to be of a given minimal size. Each contiguous "blob" with a given circumference of N * this minimal size, can only connect to at most N other blobs.

No, there is no minimal size, just that we only consider two regions as being "in contact" and therefore requiring different colours) if they have a shared boundary, and that boundary is of non-zero length.

There is no limit to how many regions can surround and be in contact with a given region, it's just that the shared border that defines "in contact with" must be of non-zero length.

Note also: we are dealing with finite maps. That means that for any given map there will be a shortest boundary for that map, but it doesn't mean there is a minimum constraint.

The four colour theorem does generalize to infinite planar graphs, in the sense that if an infinite graph can be embedded in the plane without overlaps, then a four-colouring is possible. It's a straightforward consequence of the compactness theorem for propositional logic, which I set as an exercise for my students when I teach the topic.

The "countries" are supposed to share an edge. An edge, no matter how small, breaks the cross.

https://blog.artsper.com/wp-content/uploads/2022/08/escher-2...

Consider the gray pixel in the center a placeholder, much like Escher's place holder in the above image (because he couldn't think of how to realistically depict what turns out to be the infinite fractal nature of the center)

> An edge, no matter how small breaks the cross.

My very weak intuition says that an edge of infinite smallness would not.

"... an edge of infinite smallness ..." is not a well-defined concept, and is not allowed in the original formation of the problem. Otherwise take a circle and divide it into N segments "like a pizza". They all meet in the middle in an "edge of infinite smallness", so that would require N colours.

Now make N as large as you like.

So allowing this makes the problem uninteresting, and precluding it makes the problem interesting and hard.

An "edge of infinite smallness" is a point.

(I don't recall details - but the preconditions of the Four Colour Theorem rule out all the fuzzy sets, infinitely crooked lines, "this region is all points with one rational and one irrational coordinate", and other trickery that folks who've had a bit of math might otherwise be tempted by.)

Meeting at a point doesn’t count, so for example, blue could be recolored to be red.

The graph has to be planar, which means no to edges intersect (or you can move the edges so that no two edges intersect). The complete graph with 5 or more vertices isn't planar.

This is btw equivalent to a graph with 5 nodes, where all nodes are connected to every other node, which would quite obviously be impossible to colour with just 4 colours.

It's not, though. If the four corners are sharp, blue & red are not adjacent, nor are green & orange. You can re-paint blue to red and orange to green, and you're left with a proper 3-coloring. Alternately, if the grey pixel takes another color (say, red) so that blue, green and orange are all adjacent to it, then green & orange are not adjacent -- re-paint orange to green, and you get a 4-coloring. Finally, if the grey pixel is its own region, you're effectively back in the first case and you can paint it black to obtain a 3-coloring.

The thing is: those four regions can be recoloured (change green by orange).

Reply on news.ycombinator.com