I knew that 4 colours sufficed for any arbitrary map from back in the day when I learned this, but still I found it VERY rewarding by attempting to draw a map that needed 5 colors, and how intuitive this demo was for getting a "feel" for a thing that I knew only theoretically! Like I needed an impossible geometry to fit, either an area that stretched to a zero-width path (which would becomes a point, and thus 2 areas, so doesn't fit) or some other "impossible" geometry. Loved it, congrats on a really well executed idea!
It feels like something that got detached from the things that make it work during simplification. Or it could be that I just have a misunderstanding/oversight in the zero knowledge proof :).
In an unrelated note: I colored the larger graph and it didn't even play along!
Very well done, I'll try to see if my children will enjoy that already too.
> Step 2. You click any two bordering regions, and I pull off their post-its
> Step 3. You check that the revealed colors are different
I would add explicitly in step 1 that you tell me what 3 colors you used, and in step 3 that I check that the revealed colors are different from each other and are both from that set of 3. Similar in the explanation of why this should convince me.
This was so much cooler than just being told that 4 colors is enough for every map – this one will stick with me.
It would be wonderful if schools taught a bit more like this – I almost felt like I discovered it myself!
I understand that you want to emphasize the fact that no human can understand the proof with a full overview, but I wonder whether the current sentence will not make people think mathematicians are not perfectly sure of the proof.
I can't seem to wrap my head around why this isn't 3 colors.
My two cents of the ZKP illustration is that directly using hashes are more likely to convince "computer-friendly" people to introduce the commitment scheme.
I think "very difficult" is misleading here. It implies there is an answer if you try hard enough.
https://en.wikipedia.org/wiki/Snark_(graph_theory)
First is that "One of the equivalent forms of the four color theorem is that every snark is a non-planar graph". Second, is as strengthened form of the four color theorem: "every snark has the Petersen graph as a minor", which is kind of proven (already 25 years ago), but still lacks 1 paper: https://thomas.math.gatech.edu/FC/generalize.html https://math.stackexchange.com/questions/3692582/what-is-the...
And another related concept is of nowhere-zero flows, and even more stronger conjecture that "every bridgeless graph with no Petersen minor has a nowhere zero 4-flow". https://en.wikipedia.org/wiki/Nowhere-zero_flow
And there I sit, knowing that every map of CONTIGUOUS territories can be colored with 4 colors - but on real world maps, there are enclaves - little islands that belong to a country that they have not connection to. And if those shall have the same color as their parent country, then 4 colors is not enough...
So I pick the answer "NO".
> you are wrong!!!!! every map can be colored with 4 colors! it has been proven!!!!!
(I bought Paul Lockhart's "measurements" but gave up because I felt like I needed a sandbox to play with and little hints. Like, I don't want to be told the answer but I want to know feedback exactly like this demo. Very simple: "this is not right" or "this is right, but can be done with fewer")
(My dream is to have a little game jam where we make interactive versions of these concepts as puzzle)
In order to need 5 colors, you'd need to construct a graph with 5 nodes where each of the nodes connects to all other nodes, but without any edges crossing: https://imgur.com/U52SFSi
You can just tell after playing around with the graph that it's impossible to move the nodes around on a 2d plane without an edge crossing; you need a 3rd dimension.
The final though seemed like a huge leap for me, who don’t know anything about those math mysteries (which I assume is your target audience).
First I was curious to learn how is the fast way to understand that 1, 2, or 4 colors suffice. And why finding out such a way for 3 is so hard.
The zero-knowledge proof demonstration felt like “changing the subject”. Probably I missed the connection there.
Very nice wording on the 5-color challenge! I think it was the perfect balance.
One thing I was missing was the ability to move the points already on canvas. I assume you already considered, though. (As well as right-click-to-remove?)
Well beyond effectively trivial ones where you try over and over again.
But the algorithm for coloring with five is pretty easy (relatively speaking still involves fun graph theory)
There’s not a 100% great term for the collective unit of land. Generally people go with “UK & Ireland” if they’re trying to be sensitive.
On another note, I dislike how “Zero-Knowledge Proofs” are called proofs. It’s not a proof. You iteratively increase your belief that the result is true, like in experimentation, but that’s not a proof.
I knew the 4-colour theorem but the zero knowledge proof illustration was great. I didn't get it initially but the FAQ cleared it up and I felt like I learned something as it wasn't obvious on the first look.
Only thing I would change is to make it so clicking on the picture doesn't trigger a text select, it was hard to play because a context menu kept popping up every time I changed map color.
Good job, would love to see more.
As a suggestion, I would dearly enjoy a follow-up rigorously connecting those visual, intuitive ideas to actual mathematics.
3 was a lot harder than expected — a great exercise for anyone honestly. I'm a math nerd so this was cool visualized!
Well in the end it was fun, but the warning is very misleading at least from a game perspective. I have played games at the same level but it certainly wasnt this hard, haha...
But hey, saying that it was difficult, was the only thing that kept me going for 2hrs, only to be annoyed and have a face palm moment after seeing the answer.
Nonetheless it's good post
Thanks a lot for the game. I really enjoyed it and it got me thinking about the coloring problem.
I wonder if it could be interesting to also add some bits of the corresponding graph problem into the game. This might be able to make the coloring problem a bit less "mysterious", but not less interesting.
Some shower thoughts:
It's easy to see that if you start with an arbitrary "country map", you can easily convert it into a graph with the same coloring properties: Just draw a node into the center of each region, then, if two regions have a shared border somewhere, connect their nodes with an edge.
The coloring problem is now the task of coloring all the nodes, so that no two nodes that are directly connected with an edge have the same color.
The solution to that task is also easy to see: If you have n nodes where each nodes has edges to all the other nodes, then you need n colors. The more "missing" edges you have in the graph, the less colors you can get away with. (The location of the missing edges is important though: As soon as there a group of n fully connected nodes, you need at least n colors, no matter how many additional nodes and missing edges there are)
Does that mean you can construct graphs that need 5 colors or more? Yes, just make the desired number of nodes and draw edges between all of them.
So then, where does the limit of 4 come from? There it gets interesting: Because not every graph con be converted back into a country map: Only planar graphs, i.e. graphs where no edges cross if you lie it out on a plane have a corresponding country map, otherwise you'll get an "impossible geometry".
So the coloring problem "really" shows that you can have at most 4 fully connected nodes in a planar graph - if you have graphs with more connections, you will always have at least two edges crossing, no matter how you arrange the nodes and edges on the plane.
This might also explain why it is so hard to produce good visualisations for arbitrary graphs.
An interesting question might be how the planar criterion works for other geometries, e.g. if you lay out the graph on a sphere or torus or multi-hole torus.
Another aside: In real life, states are not always continous regions on a map. There are a lot of nations that have enclaves, oversea territories or for other reasons consist of more than one geographical region. So in theory, a "map of nation states" instead of a "map of regions" could represent a nonplanar graph and could have a coloring number greater than 4. I'm not sure if there is actually such a situation anywhere on the globe though.
[1] sorry, 3-chromatic or whatever
Thanks for leading us down this mathematical rabbit hole today.